path: root/Notes/MIR-Optimisations.md

% MIR Optimisations (Design Notes)

De-Tuple
========

Purpose: Remove useless tuples created in `match (a, b) { (a,b) => { ... }}`

Algorithm
---------

Detect `Local(N) = Tuple(...)` and record.
If the contents of the tuple is invalidated, delete the record
If a recorded local is moved, delete record
If a recorded local is mutated, delete record
If a recorded local is used via field access, record the field and location
- If a field is accessed twice, delete the record

At the end of the block, remove original tuple assignment and propagate the values to destinations.


Simple De-Temporary
===================

Purpose: Remove single-use temporaries
`_1 = ...; _2 = _1` -> `_2 = ...`

Algorithm
---------

- Locate locals that are only every read/written once
- If the use is an assignment AND the destination isn't invalidated between the first assign and second
 - Replace the original assignment with the second destination


De-Temporary (version 1)
========================

Purpose: Eliminate useless temporaries
```
_1 = _0.1
_2 = foo(_1)
```

Algorithm
---------

- 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.

- 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
----------

```
for stmt in block.statements
{
    check_for_mutate_or_borrow_of_dest();
    check_for_mutate_or_move_of_source();
    do_replacements(stmt);
    if let Assign(e) = stmt
    {
       if let Local(idx) = e.dst && let Use(_) = e.src
       {
           assign_list.insert(idx, stmt_idx)
       }
    }
}

fn do_replacements(stmt)
{
    visit_lvalues(stmt, |lv, usage| {
        top_level = true;
        // 1. Search for replacements
        visit_lvalues(lv, |ilv, usage2| {
            if Local(i) == ilv {
                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)
        return true;
        });
}
```


Reverse De-temporary
====================

Allows removing useless temporaries (e.g. function returns)

IDEA ONLY.
- Find `... = Local(n)`
- Find where it was defined
- If the destination was invalidated in that time, don't do anything
- If it's mutated or otherwise accessed in the intervening time, don't do anything with it
- If the value is Copy and it's used elsewhere, don't do anything
- Otherwise, remove the assignment and move upwards

Return Backprop
===============

Purpose: Eliminate useless temporaries in creating the return value

Locate `RETURN = Local(N)` and replace use of Local(N) as assignment destination with RETURN

Note: Only replace assignments that are setting the value that will become the return value.

Algorithm
---------
TODO: 

Pseudocode
----------
TODO: 


Dead Assignment Elimination
===========================

Purpose: Remove dead code from previous passes

Remove assignments where the assigned value isn't read/borrowed before next assign

Algorithm
---------
- For all assignments of the form `Local(n) = ...`, seek forwards until the next use or loopback
- If the next use of that particular lvalue is an assignment, delete the original assignment
- If the lvalue is fully reassigned, delete the original assignment
  - Fully reassignment means that the LHS of Index/Field is mutated

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


Borrow Elimination
==================
Purpose: Remove borrows generated by method calls that have been inlined

Overview
--------
- Find locals that are only assigned once, and only ever used via a deref
  operation.
  - Allow drops to use the destination by value
- If the assignment was a Borrow RValue, continue
- Iterate forward, replacing usage of the value with the original source while:
  - The source isn't invalidated
  - The number of replacements is less than the number of known usage sites
- If the original borrow itself contained a deref of a local, update that
  local's usage count.
- If all usage sites were updated, erase the original borrow


Borrow Elimination 2
====================
Purpose: Remove borrows of borrows that are never used again

Overview
--------
- Find assign-once/use-once locals (ignoring drop)
- If the source is a borrow of a deref of a local/argument, continue
- If the source inner value is of the same type as the local, continue
  - I.e. we're not re-borrowing a `&mut` as `&`
- If the variable's type is not `&` (i.e. it's &mut or &uniq)
  - Check the usage count for the source value, and only continue is this is
    the only usage site of the source
  - Ideally: This would only check forwards, but that's hard
- If the variable's type is `&`, check the path between assignment and usage
  for invalidation.
- If no invalidation found, replace usage with inner of assignment and erase
  assignment.


Slice Transmute
===============
Purpose: Detect places where slices are createdby transmuting from a (usize,usize) and replace with
dedicated MIR statement.

Overview
--------
- Find transmute calls with a destination type of `&[T]`
- Check the input type:
  - `(usize,usize)` : good
  - `struct Foo { usize, usize }` : good
- Check if the input was a use/write once local
- Locate assignment of input
  - Check if it was a struct/tuple literal
- Remove assignment, replace transmute with at `MAKEDST` op