MIR Optimise - Redo DeTemporary pass, works for build rustc/cargo, rustc tested

2 files changed, 199 insertions, 146 deletions

diff --git a/Notes/MIR-Optimisations.md b/Notes/MIR-Optimisations.md
index 759bfa2e..e83f7cd3 100644
--- a/Notes/MIR-Optimisations.md
+++ b/Notes/MIR-Optimisations.md
@@ -19,8 +19,8 @@ At the end of the block, remove original tuple assignment and propagate the valu
 
 
 
-De-Temporary
-============
+De-Temporary (version 1)
+========================
 
 Purpose: Eliminate useless temporaries
 ```
@@ -31,20 +31,19 @@ _2 = foo(_1)
 Algorithm
 ---------
 
-Where the pattern `Local(N) = Use(...)` is seen, record that statement as the assignment for `Local(N)`.
+- Where the pattern `Local(N) = Use(...)` is seen, record that statement as the assignment for `Local(N)`.
+- Detect any uses of `Local(N)` in mutation context (e.g. `Field(Local(N), 0) = ...`) or as a borrow and remove from the
+  list (as these cause the local to diverge from its source).
+- Detect any by-value or mutation uses of the origin value that would mean that moving the assignment forwards would
+  lead to a use-after-free or incorrect value.
 
-Detect any uses of `Local(N)` in mutation context (e.g. `Field(Local(N), 0) = ...`) or as a borrow and remove from the
-list (as these cause the local to diverge from its source).
-
-Detect any by-value or mutation uses of the origin value that would mean that moving the assignment forwards would
-lead to a use-after-free or incorrect value.
-
-If a recorded local is used, replace that usage by the original source. If the value was !Copy, and the use is a move,
- delete the original assignment.
-- CATCH: Detecting a by-move of !Copy is hard when a Copy value is used from a !Copy struct, needs knowledge of the
-  types involved.
-- CATCH: Since partial moves are valid, the !Copy rule above is invalid if it would have been a partial move.
-  - Only allow use of a !Copy result when it's just the slot.
+- Find any uses of locals recorded locals
+  - If this is of a Copy value, the replacement
+    - Copy values can be reused freely
+  - If the value is used at the top level of the source RValue, do the replacemnet and remove the record
+    - !Copy value moved, so can't be moved again.
+  - Otherwise, remove the record
+    - The value was used, so then assignment can't be replaced with later and deleted.
 
 Pseudocode
 ----------
@@ -67,15 +66,22 @@ for stmt in block.statements
 fn do_replacements(stmt)
 {
     visit_lvalues(stmt, |lv, usage| {
-        // 1. Check if Copy (if it is, don't delete any referenced values)
-        delete = (usage == Move && !lv_is_copy(lv));
-        // 2. Search for replacements
+        top_level = true;
+        // 1. Search for replacements
         visit_lvalues(lv, |ilv, usage2| {
             if Local(i) == ilv {
-               ilv = replacement;
-               if delete {
-                    remove_replacement;
-               }
+                if replacement = find_replacement(i) {
+                    if is_copy(ilv) {
+                        ilv = replacement
+                    }
+                    else if top_level {
+                        ilv = replacement
+                        remove_replacement(i)
+                    }
+                    else {
+                        remove_replacement(i)
+                    }
+                }
             }
             });
         // Early-return (don't recuse)
@@ -95,6 +101,13 @@ Locate `RETURN = Local(N)` and replace use of Local(N) as assignment destination
 
 Note: Only replace assignments that are setting the value that will become the return value.
 
+Algorithm
+---------
+TODO: 
+
+Pseudocode
+----------
+TODO: 
 
 
 Dead Assignment Elimination
@@ -104,14 +117,56 @@ Purpose: Remove dead code from previous passes
 
 Remove assignments where the assigned value isn't read/borrowed before next assign
 
+Algorithm
+---------
+
+Pseudocode
+---------
+
+Dead Drop Flag Elimination
+==========================
+
+Purpose: Remove unused (or unchanged) drop flags
+
+Algorithm
+---------
+- Enumerate all changes to drop flags
+- If a flag is never set, replace all uses with its default and delete
+- If a flag is never used, delete
+
+
 Constant Propagation
 ====================
 
 Purpose: Allow deletion of useless code (`if false`) and expansion of `size_of` (and relevant optimisations)
 
+Algorithm
+---------
+- Track assignments of slots with constants
+- Erase record if the slot is invalidated
+- Replace usage of the slot where possible with the constant
+- Evaluate BinOps with both arguments a known slot
+
 
 Value Forward Propagation
 =========================
 
 Purpose: Determine when a value has the same value in all paths to a BB and move the assignment into that BB
 
+Inlining
+========
+
+Purpose: Inline simple methods
+
+Algorithm
+---------
+- For each function call:
+- Check if the called function is simple enough to be inlined
+  - A single BB - inline
+  - Three bbs (first being a function call) - inline
+  - First bb ends with a switch of a constant parameter, and all arms point to return or a return bb
+
+CFG Simplification
+==================
+Purpose: Remove gotos to blocks that only have a single use
+
diff --git a/src/mir/optimise.cpp b/src/mir/optimise.cpp
index 08e246df..11cbe45e 100644
--- a/src/mir/optimise.cpp
+++ b/src/mir/optimise.cpp
@@ -79,7 +79,7 @@ namespace {
             return visit_mir_lvalue_mut(*e.val, u == ValUsage::Move ? ValUsage::Read : u, cb);
             ),
         (Deref,
-            return visit_mir_lvalue_mut(*e.val, ValUsage::Read, cb);
+            return visit_mir_lvalue_mut(*e.val, u == ValUsage::Borrow ? u : ValUsage::Read, cb);
             ),
         (Index,
             bool rv = false;
@@ -241,6 +241,10 @@ namespace {
             )
         )
     }
+    void visit_mir_lvalues(const ::MIR::Terminator& term, ::std::function<bool(const ::MIR::LValue& , ValUsage)> cb)
+    {
+        visit_mir_lvalues_mut(const_cast<::MIR::Terminator&>(term), [&](auto& lv, auto im){ return cb(lv, im); });
+    }
 
     void visit_mir_lvalues_mut(::MIR::TypeResolve& state, ::MIR::Function& fcn, ::std::function<bool(::MIR::LValue& , ValUsage)> cb)
     {
@@ -555,15 +559,12 @@ void MIR_Optimise(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path
         MIR_Validate(resolve, path, fcn, args, ret_type);
         #endif
 
-        // Disabled: Slightly buggy.
-#if 0
         // Attempt to remove useless temporaries
         while( MIR_Optimise_DeTemporary(state, fcn) )
             change_happened = true;
 #if CHECK_AFTER_ALL
         MIR_Validate(resolve, path, fcn, args, ret_type);
 #endif
-#endif
 
         // >> Replace values from composites if they're known
         //   - Undoes the inefficiencies from the `match (a, b) { ... }` pattern
@@ -1254,161 +1255,158 @@ bool MIR_Optimise_DeTemporary(::MIR::TypeResolve& state, ::MIR::Function& fcn)
     for(unsigned int bb_idx = 0; bb_idx < fcn.blocks.size(); bb_idx ++)
     {
         auto& bb = fcn.blocks[bb_idx];
-        // TODO: Store statement index, to allow deleting the statement if the value is !Copy
-        ::std::vector<unsigned> to_delete;
-        ::std::map<unsigned,unsigned>   local_assignments;  // Local index to statement
-        // Since the passed lvalue was mutated (or borrowed), check if that invalidates part of the above cache.
-        auto check_invalidates = [&](const ::MIR::LValue& lv) {
-            for(auto it = local_assignments.begin(); it != local_assignments.end(); )
-            {
-                const auto& new_lv = bb.statements.at( it->second ).as_Assign().src.as_Use();
+        ::std::map<unsigned,unsigned>   local_assignments;  // Local number -> statement index
+        ::std::vector<unsigned> statements_to_remove;   // List of statements that have to be removed
+
+        // ----- Helper closures -----
+        // > Check if a recorded assignment is no longer valid.
+        auto cb_check_invalidate = [&](const ::MIR::LValue& lv, ValUsage vu) {
+                for(auto it = local_assignments.begin(); it != local_assignments.end(); )
+                {
+                    bool invalidated = false;
+                    const auto& src_rvalue = bb.statements[it->second].as_Assign().src;
 
-                bool new_invalidated = visit_mir_lvalue(new_lv, ValUsage::Read, [&](const auto& ilv2, auto) {
-                    return visit_mir_lvalue(lv, ValUsage::Write, [&](const auto& ilv, auto vu) {
-                        if( ilv == ilv2 )
+                    // Destination invalidated?
+                    if( lv.is_Local() && it->first == lv.as_Local() )
+                    {
+                        switch(vu)
                         {
-                            if( vu != ValUsage::Read )
-                                return true;
-                            if( !state.lvalue_is_copy(ilv) )
-                                return true;
-                            DEBUG(state << it->first << " referenced, but not invalidated");
+                        case ValUsage::Borrow:
+                        case ValUsage::Write:
+                            DEBUG(state << "> Mutate/Borrowed " << lv);
+                            invalidated = true;
+                            break;
+                        default:
+                            break;
                         }
-                        return false;
-                        });
-                    });
-                bool old_used = visit_mir_lvalue(lv, ValUsage::Write, [&](const auto& ilv, auto vu) {
-                    if( ilv == ::MIR::LValue::make_Local(it->first) )
+                    }
+                    // Source invalidated?
+                    else
                     {
-                        DEBUG(state << it->first << " used, remove");
-                        return true;
+                        switch(vu)
+                        {
+                        case ValUsage::Borrow:  // Borrows are annoying, assume they invalidate anything used
+                        case ValUsage::Write:   // Mutated? It's invalidated
+                        case ValUsage::Move:    // Moved? Now invalid
+                            visit_mir_lvalues(src_rvalue, [&](const auto& s_lv, auto /*s_vu*/) {
+                                if( s_lv == lv )
+                                {
+                                    DEBUG(state << "> Invalidates source of Local(" << it->first << ") - " << src_rvalue);
+                                    invalidated = true;
+                                    return true;
+                                }
+                                return false;
+                                });
+                            break;
+                        case ValUsage::Read:    // Read is Ok
+                            break;
+                        }
                     }
-                    return false;
-                    });
 
-                if( new_invalidated || old_used )
-                {
-                    DEBUG(state << it->first << " from " << bb_idx << "/" << it->second << " - Invalidated");
-                    it = local_assignments.erase(it);
-                }
-                else
-                {
-                    ++ it;
+                    if( invalidated )
+                    {
+                        it = local_assignments.erase(it);
+                    }
+                    else
+                    {
+                        ++ it;
+                    }
                 }
-            }
+                return false;
             };
-        auto replace_cb = [&](auto& lv, auto use) {
-            if( lv.is_Local() && (use == ValUsage::Read || use == ValUsage::Move) )
-            {
-                auto it = local_assignments.find(lv.as_Local());
-                if( it != local_assignments.end() )
+            // ^^^ Check for invalidations
+        auto cb_apply_replacements = [&](auto& top_lv, auto top_usage) {
+            // NOTE: Visits only the top-level LValues
+            // - The inner `visit_mir_lvalue_mut` handles sub-values
+
+            // TODO: Handle partial moves (only delete assignment if the value is fully used)
+            // > For now, don't do the replacement if it would delete the assignment UNLESS it's directly being used)
+
+            // 2. Search for replacements
+            bool top_level = true;
+            visit_mir_lvalue_mut(top_lv, top_usage, [&](auto& ilv, auto /*i_usage*/) {
+                if( ilv.is_Local() )
                 {
-                    auto new_lv = bb.statements.at( it->second ).as_Assign().src.as_Use().clone();
-                    if( !state.m_resolve.type_is_copy(state.sp, fcn.locals[lv.as_Local()]) )
+                    auto it = local_assignments.find(ilv.as_Local());
+                    if( it != local_assignments.end() )
                     {
-                        local_assignments.erase(it);
-                        return false;
-                        // TODO: ::Move is used for field accesses, even if the value is !Copy
-                        if( use == ValUsage::Move )
+                        // - Copy? All is good.
+                        if( state.lvalue_is_copy(ilv) )
                         {
-                            to_delete.push_back(it->second);
+                            ilv = bb.statements[it->second].as_Assign().src.as_Use().clone();
+                            DEBUG(state << "> Replace (and keep) Local(" << it->first << ") with " << ilv);
+                        }
+                        // - Top-level (directly used) also good.
+                        else if( top_level )
+                        {
+                            // TODO: DstMeta/DstPtr _doesn't_ move, so shouldn't trigger this.
+                            ilv = bb.statements[it->second].as_Assign().src.as_Use().clone();
+                            DEBUG(state << "> Replace (and remove) Local(" << it->first << ") with " << ilv);
+                            statements_to_remove.push_back( it->second );
                             local_assignments.erase(it);
-                            DEBUG(state << lv << " -> " << new_lv << " (and erase)");
                         }
+                        // - Otherwise, remove the record.
                         else
                         {
+                            DEBUG(state << "> Non-copy value used within a LValue, remove record of Local(" << it->first << ")");
                             local_assignments.erase(it);
-                            DEBUG(state << lv << " kept, !Copy and not moved");
-                            return false;
                         }
                     }
-                    else
-                    {
-                        DEBUG(state << lv << " -> " << new_lv);
-                    }
-                    lv = mv$(new_lv);
-                    changed = true;
-                    return true;
                 }
-            }
-            return false;
+                top_level = false;
+                return false;
+                });
+            // Return true to prevent recursion
+            return true;
             };
+
+        // ----- Top-level algorithm ------
+        // - Find expressions matching the pattern `Local(N) = Use(...)`
+        //  > Delete entry when destination is mutated
+        //  > Delete entry when source is mutated or invalidated (moved)
         for(unsigned int stmt_idx = 0; stmt_idx < bb.statements.size(); stmt_idx ++ )
         {
             auto& stmt = bb.statements[stmt_idx];
             state.set_cur_stmt(bb_idx, stmt_idx);
             DEBUG(state << stmt);
 
-            // 2. If it's an assignment of the form Local(N) = LValue, keep a record of that.
-            //  > If a local is borrowed, wipe that local's record
-            bool something_to_add = false;
-            ::std::pair<unsigned,unsigned>  to_add;
-            if(const auto* e = stmt.opt_Assign())
-            {
-                if( const auto* se = e->src.opt_Borrow() )
-                {
-                    if( se->val.is_Local() ) {
-                        local_assignments.erase( se->val.as_Local() );
-                    }
-                    check_invalidates(se->val);
-                }
-                if( e->dst.is_Local() )
-                {
-                    if( e->src.is_Use() )
-                    {
-                        to_add = ::std::make_pair(e->dst.as_Local(), stmt_idx);
-                        something_to_add = true;
+            // - Check if this statement mutates or borrows a recorded local
+            //  > (meaning that the slot isn't a temporary)
+            // - Check if this statement mutates or moves the source
+            //  > (thus making it invalid to move the source forwards)
+            visit_mir_lvalues(stmt, cb_check_invalidate);
 
-                        if( visit_mir_lvalues(e->src, [&](const auto& lv, auto ){ return lv == e->dst; }) )
-                        {
-                            DEBUG(state << "Assignment to slot used in source, can't use");
-                            something_to_add = false;
-                        }
-                    }
-                    local_assignments.erase( e->dst.as_Local() );
-                }
-                check_invalidates(e->dst);
+            // - Apply known relacements
+            visit_mir_lvalues_mut(stmt, cb_apply_replacements);
 
-                // Remove no-op assignents
-                if( TU_TEST1(e->src, Use, == e->dst) ) {
-                    bb.statements.erase(bb.statements.begin() + stmt_idx);
-                    stmt_idx -= 1;
-                    continue ;
-                }
-            }
-            else if( stmt.is_Drop() )
-            {
-                check_invalidates(stmt.as_Drop().slot);
-            }
-            else
+            // - Check if this is a new assignment
+            if( stmt.is_Assign() && stmt.as_Assign().dst.is_Local() && stmt.as_Assign().src.is_Use() )
             {
+                local_assignments.insert(::std::make_pair( stmt.as_Assign().dst.as_Local(), stmt_idx ));
+                DEBUG(state << "> Record assignment");
             }
-            if( !something_to_add )
-            {
-                // 1. Replace any referenced locals with contents of a record of the local values.
-                //  > Don't do the replacement if the source could have changed
-                visit_mir_lvalues_mut(stmt, replace_cb);
-            }
-
-            visit_mir_lvalues(stmt, [&](const auto& lv, auto vu){
-                if(vu == ValUsage::Move)
-                    check_invalidates(lv);
-                return true;
-                });
+        } // for(stmt in bb.statements)
 
-            if( something_to_add ) {
-                DEBUG(state << "Record Local(" << to_add.first << ") set from here");
-                local_assignments.insert(to_add);
-            }
-        }
+        // TERMINATOR
         state.set_cur_stmt_term(bb_idx);
         DEBUG(state << bb.terminator);
-        visit_mir_lvalues_mut(bb.terminator, replace_cb);
+        // > Check for invalidations (e.g. move of a source value)
+        visit_mir_lvalues(bb.terminator, cb_check_invalidate);
+        // > THEN check for replacements
+        if( ! bb.terminator.is_Switch() )
+        {
+            visit_mir_lvalues_mut(bb.terminator, cb_apply_replacements);
+        }
 
-        ::std::sort(to_delete.begin(), to_delete.end());
-        while(!to_delete.empty())
+        // Remove assignments
+        ::std::sort(statements_to_remove.begin(), statements_to_remove.end());
+        while(!statements_to_remove.empty())
         {
-            bb.statements.erase( bb.statements.begin() + to_delete.back() );
-            to_delete.pop_back();
+            // TODO: Handle partial moves here?
+            // TODO: Is there some edge case I'm missing where the assignment shouldn't be removed?
+            // > It isn't removed if it's used as a Copy, so that's not a problem.
+            bb.statements.erase( bb.statements.begin() + statements_to_remove.back() );
+            statements_to_remove.pop_back();
         }
     }