# Escape Analysis MTG @ 2021/06/07

# From abstract interpretation point of view

## Current States of pointer/alias analysis

Some of pointer/alias analysis is already performed, but very limitedly.

Within our current lattice implementation, "must-alias" information is essentially same as object identity,
which can be only exploited for `Const` objects,
and so exact pointer value information is known only for `Const` and `PartialStruct`.

julia> # constant folding
       struct Foo
           foo
       end

julia> code_typed(; optimize=false) do
           f1 = Foo(1)            # Const(Foo(1))
           f2 = f1                # Const(Foo(1))
       
           # alias information
           r1 = f1 === f2         # Const(true), i.e. "must-alias"
           r2 = f1.foo === f2.foo # (Const(1), Const(1)), pointers are fully known
       
           return r1, r2
       end |> first
CodeInfo(
1 ─      (f1 = Main.Foo(1))::Core.Const(Foo(1))
│        (f2 = f1::Core.Const(Foo(1)))::Core.Const(Foo(1))
│        (r1 = f1::Core.Const(Foo(1)) === f2::Core.Const(Foo(1)))::Core.Const(true)
│   %4 = Base.getproperty(f1::Core.Const(Foo(1)), :foo)::Core.Const(1)
│   %5 = Base.getproperty(f2::Core.Const(Foo(1)), :foo)::Core.Const(1)
│        (r2 = %4 === %5)::Core.Const(true)
│   %7 = Core.tuple(r1::Core.Const(true), r2::Core.Const(true))::Core.Const((true, true))
└──      return %7
) => Tuple{Bool, Bool}

julia> # partial constant folding
       struct FooPartial
           foo1
           foo2
       end

julia> code_typed((Any,); optimize=false) do foo2
           f1 = FooPartial(1, foo2)  # PartialStruct(FooPartial, Any[Const(1), Any])
           f2 = f1                   # PartialStruct(FooPartial, Any[Const(1), Any])
       
           # alias information
           r1  = f1      === f2      # Bool, not unknown
           r21 = f1.foo1 === f2.foo1 # Const(true), pointers can be partially known
           r22 = f1.foo2 === f2.foo2 # Bool, not known
           @assert f1.foo2 === f2.foo2
           r23 = f1.foo2 === f2.foo2 # Bool, not known even if we manually asserted
       
           return r1, r21, r22, r23
       end |> first
CodeInfo(
1 ─       Core.NewvarNode(:(r23))::Any
│         (f1 = Main.FooPartial(1, foo2))::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any])
│         (f2 = f1::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]))::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any])
│         (r1 = f1::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]) === f2::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]))::Bool
│   %5  = Base.getproperty(f1::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo1)::Core.Const(1)
│   %6  = Base.getproperty(f2::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo1)::Core.Const(1)
│         (r21 = %5 === %6)::Core.Const(true)
│   %8  = Base.getproperty(f1::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo2)::Any
│   %9  = Base.getproperty(f2::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo2)::Any
│         (r22 = %8 === %9)::Bool
│   %11 = Base.getproperty(f1::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo2)::Any
│   %12 = Base.getproperty(f2::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo2)::Any
│   %13 = (%11 === %12)::Bool
└──       goto #3 if not %13
2 ─       goto #4
3 ─ %16 = Base.AssertionError("f1.foo2 === f2.foo2")::Any
└──       Base.throw(%16)::Union{}
4 ┄ %18 = Base.getproperty(f1::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo2)::Any
│   %19 = Base.getproperty(f2::Core.PartialStruct(FooPartial, Any[Core.Const(1), Any]), :foo2)::Any
│         (r23 = %18 === %19)::Bool
│   %21 = Core.tuple(r1, r21::Core.Const(true), r22, r23)::Core.PartialStruct(NTuple{4, Bool}, Any[Bool, Core.Const(true), Bool, Bool])
└──       return %21
) => NTuple{4, Bool}

Currently `Const` and `PartialStruct` don't handle `mutable struct` objects because we don't track scope of pointers (this is an escape information ?)
(especially, handled [here](https://github.com/JuliaLang/julia/blob/0a246488f87203ffe11f60f3a506b9db83298b6c/base/compiler/abstractinterpretation.jl#L1431)).

julia> mutable struct FooMutable
           foo
       end

julia> code_typed(; optimize=false) do
           f1 = FooMutable(1)     # FooMutable
           f2 = f1                # FooMutable
       
           # alias information
           r1 = f1 === f2         # Bool, not known
           r2 = f1.foo === f2.foo # Bool, not known
       
           return r1, r2
       end |> first
CodeInfo(
1 ─      (f1 = Main.FooMutable(1))::FooMutable
│        (f2 = f1)::FooMutable
│        (r1 = f1 === f2)::Bool
│   %4 = Base.getproperty(f1, :foo)::Any
│   %5 = Base.getproperty(f2, :foo)::Any
│        (r2 = %4 === %5)::Bool
│   %7 = Core.tuple(r1, r2)::Tuple{Bool, Bool}
└──      return %7
) => Tuple{Bool, Bool}

## Improvement ideas

### Local pointer analysis improvement

- We can introduce new lattice like `ConstrainableField` and `ConstainableStruct`,
to improve local pointer information a bit more
E.g.:

julia> struct Foo
           foo
       end

julia> code_typed((Foo,); optimize=false) do foo
           # foo :: ConstainableStruct(Foo, Any[])
           if isa(foo.foo, Int) # foo.foo :: ConstrainableField(SlotNumber(2), :foo, Int)
               # foo :: ConstainableStruct(Foo, Any[(:foo, Int)])
               return foo.foo # :: Int
           end
       end |> first
CodeInfo(
1 ─ %1 = Base.getproperty(foo, :foo)::Any
│   %2 = (%1 isa Main.Int)::Bool
└──      goto #3 if not %2
2 ─ %4 = Base.getproperty(foo, :foo)::Any
└──      return %4
3 ─      return nothing
) => Any

- Still limited to `struct`, because we lack escape information
- probably we can't use these lattices for "must-alias" information

## Escape analysis

Once escape analysis is landed, we may be able to enable (partial) constant-folding on `mutable struct`s
and do something like `ConstrainableField/Struct` stuff for them.

julia> mutable struct FooMutable
           foo
       end

julia> code_typed(; optimize=false) do
           # now we know both `f1` and `f2` doesn't escape this scope, we can constant-fold them
       
           f1 = FooMutable(1)     # Const(FooMutable(1))
           f2 = f1                # Const(FooMutable(1))
       
           # alias information
           r1 = f1 === f2         # Const(true)
           r2 = f1.foo === f2.foo # Const(true)
       
           return r1, r2
       end |> first
CodeInfo(
1 ─      (f1 = Main.FooMutable(1))::FooMutable
│        (f2 = f1)::FooMutable
│        (r1 = f1 === f2)::Bool
│   %4 = Base.getproperty(f1, :foo)::Any
│   %5 = Base.getproperty(f2, :foo)::Any
│        (r2 = %4 === %5)::Bool
│   %7 = Core.tuple(r1, r2)::Tuple{Bool, Bool}
└──      return %7
) => Tuple{Bool, Bool}

Considerations:
- this motivates doing escape analysis _during_ inference
- but escape analysis is probably better to be implemented as a post-inference process, so we may not be able to exploit the information during abstract interpret..
* but escape information might be hard to drive without type information

# Questions

- is it reasonable to think of usages of escape information for optimizaitons, _fully on Julia-level_ ?
- some possible optimizations (from [wiki](https://en.wikipedia.org/wiki/Escape_analysis)):
* **scalar replacement:**: will be possible as an optimization pass
* **heap allocations to stack allocations**: how to enable this on Julia level ? introduce meta label ?
* synchronization elision: almost sure this is out of our scope for the time being

# Discussions

- target `mutable struct`s
* finalizers ?
* no escape, then unbox ?
- recursive calls
* self-recursive isn't a probrem
* mutually-recursive is an evil
* but the complicated cycle handling is only necessary for inference, and for a separated escape analysis pass, we can just write a simple code to handle cycles ?
* two different sources of alias approach
* find alias bindings: by abstract interpretation
* use allocation sites: what LLVM does it already