Skip to content

optimizer: compute side-effect-freeness for array allocations#43565

Merged
aviatesk merged 1 commit intomasterfrom
avi/arrayalloc
Dec 30, 2021
Merged

optimizer: compute side-effect-freeness for array allocations#43565
aviatesk merged 1 commit intomasterfrom
avi/arrayalloc

Conversation

@aviatesk
Copy link
Copy Markdown
Member

@aviatesk aviatesk commented Dec 27, 2021

This would be useful for future Julia-level optimizations on arrays.
Initially I want to have this in order to add array primitives support
in EscapeAnalysis.jl, which should help us implement a variety of array
optimizations including dead array allocation elimination, copy-elision
from Array to ImmutableArray conversion (#42465), etc., but I found
this might be already useful for us since this enables some DCE in very
simple cases for free:

julia> function simple!(x::T) where T
           d = IdDict{T,T}() # dead alloc
           # ... computations that don't use `d` at all
           return nothing
       end
simple! (generic function with 1 method)

julia> @code_typed simple!("foo")
CodeInfo(
1 ─     return Main.nothing
) => Nothing

This enhancement is super limited though, e.g. DCE won't happen when
array allocation involves other primitive operations like arrayset:

julia> code_typed() do
           a = Int[0,1,2]
           nothing
       end

1-element Vector{Any}:
 CodeInfo(
1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Int64}, svec(Any, Int64), 0, :(:ccall), Vector{Int64}, 3, 3))::Vector{Int64}
│        Base.arrayset(false, %1, 0, 1)::Vector{Int64}
│        Base.arrayset(false, %1, 1, 2)::Vector{Int64}
│        Base.arrayset(false, %1, 2, 3)::Vector{Int64}
└──      return Main.nothing
) => Nothing

Further enhancement o optimize cases like above will be based on top of
incoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.

@pchintalapudi So we're working more and more similar kinds of optimizations (e.g. this could be considered as a very limited version of #43548).
Maybe we want to have some meeting to discuss which parts should be done on Julia-level or LLVM-level?

@aviatesk aviatesk added the compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) label Dec 27, 2021
@aviatesk aviatesk force-pushed the avi/arrayalloc branch 2 times, most recently from 8175f31 to d0866b9 Compare December 27, 2021 17:11
KristofferC
KristofferC reviewed Dec 27, 2021
View reviewed changes
base/reflection.jl Outdated
end
end

LLT_ALIGN(x, sz) = (x + sz - 1) & -sz
Copy link
Copy Markdown
Member

@KristofferC KristofferC Dec 27, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Perhaps put this before it is used?

This was referenced Dec 28, 2021
Closed
Closed
@aviatesk
Copy link
Copy Markdown
Member Author

aviatesk commented Dec 28, 2021

@nanosoldier runtests(ALL, vs = ":master")

@aviatesk aviatesk force-pushed the avi/arrayalloc branch 2 times, most recently from 02318a0 to 6754e8a Compare December 29, 2021 11:58
@aviatesk aviatesk requested a review from Keno December 29, 2021 11:59
@aviatesk aviatesk mentioned this pull request Dec 29, 2021
Merged
@aviatesk
optimizer: compute side-effect-freeness for array allocations
ff3cf17 
This would be useful for Julia-level optimizations on arrays.
Initially I want to have this in order to add array primitives support
in EscapeAnalysis.jl, which should help us implement a variety of array
optimizations including dead array allocation elimination, copy-elision
from `Array` to `ImmutableArray` conversion (#42465), etc., but I found
this might be already useful for us since this enables some DCE in very
simple cases like:
```julia
julia> function simple!(x::T) where T
           d = IdDict{T,T}() # dead alloc
           # ... computations that don't use `d` at all
           return nothing
       end
simple! (generic function with 1 method)

julia> @code_typed simple!("foo")
CodeInfo(
1 ─     return Main.nothing
) => Nothing
```

This enhancement is super limited though, e.g. DCE won't happen when
array allocation involves other primitive operations like `arrayset`:
```julia
julia> code_typed() do
           a = Int[0,1,2]
           nothing
       end

1-element Vector{Any}:
 CodeInfo(
1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Int64}, svec(Any, Int64), 0, :(:ccall), Vector{Int64}, 3, 3))::Vector{Int64}
│        Base.arrayset(false, %1, 0, 1)::Vector{Int64}
│        Base.arrayset(false, %1, 1, 2)::Vector{Int64}
│        Base.arrayset(false, %1, 2, 3)::Vector{Int64}
└──      return Main.nothing
) => Nothing
```

Further enhancement o optimize cases like above will be based on top of
incoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.
@aviatesk aviatesk merged commit ab4e036 into master Dec 30, 2021
@aviatesk aviatesk deleted the avi/arrayalloc branch December 30, 2021 07:30
vtjnash
vtjnash reviewed Jan 10, 2022
View reviewed changes
base/compiler/optimize.jl
return true
end

function foreigncall_effect_free(stmt::Expr, @nospecialize(rt), src::Union{IRCode,IncrementalCompact})
Copy link
Copy Markdown
Member

@vtjnash vtjnash Jan 10, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

what is the purpose of rt here? It does not look used.

vtjnash
vtjnash reviewed Jan 10, 2022
View reviewed changes
base/compiler/optimize.jl
Comment on lines +296 to +298
atype = widenconst(argextype(args[6], src))
isType(atype) || return false
atype = atype.parameters[1]
Copy link
Copy Markdown
Member

@vtjnash vtjnash Jan 10, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

use instanceof_tfunc here?

vtjnash
vtjnash reviewed Jan 10, 2022
View reviewed changes
base/compiler/optimize.jl
Comment on lines +312 to +314
atype = widenconst(argextype(args[6], src))
isType(atype) || return false
atype = atype.parameters[1]
Copy link
Copy Markdown
Member

@vtjnash vtjnash Jan 10, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

instanceof_tfunc here too?

src/jl_exported_funcs.inc
YY(LLVMExtraAddGCInvariantVerifierPass) \
YY(LLVMExtraAddDemoteFloat16Pass) \
YY(LLVMExtraAddCPUFeaturesPass) \

Copy link
Copy Markdown
Member

@vtjnash vtjnash Jan 10, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

this line is significant, don't remove it

@aviatesk
Copy link
Copy Markdown
Member Author

aviatesk commented Jan 11, 2022

Thanks for your review @vtjnash . I will make a follow up PR.

aviatesk added a commit that referenced this pull request Jan 11, 2022
@aviatesk
follow up #43565
9d97266
aviatesk added a commit that referenced this pull request Jan 11, 2022
@aviatesk
follow up #43565
c763c71
@aviatesk aviatesk mentioned this pull request Jan 11, 2022
Merged
aviatesk added a commit that referenced this pull request Jan 11, 2022
@aviatesk
follow up #43565 (#43755)
b59e852
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Feb 22, 2022
@aviatesk @LilithHafner
optimizer: compute side-effect-freeness for array allocations (JuliaL…
7fda00b 
…ang#43565)

This would be useful for Julia-level optimizations on arrays.
Initially I want to have this in order to add array primitives support
in EscapeAnalysis.jl, which should help us implement a variety of array
optimizations including dead array allocation elimination, copy-elision
from `Array` to `ImmutableArray` conversion (JuliaLang#42465), etc., but I found
this might be already useful for us since this enables some DCE in very
simple cases like:
```julia
julia> function simple!(x::T) where T
           d = IdDict{T,T}() # dead alloc
           # ... computations that don't use `d` at all
           return nothing
       end
simple! (generic function with 1 method)

julia> @code_typed simple!("foo")
CodeInfo(
1 ─     return Main.nothing
) => Nothing
```

This enhancement is super limited though, e.g. DCE won't happen when
array allocation involves other primitive operations like `arrayset`:
```julia
julia> code_typed() do
           a = Int[0,1,2]
           nothing
       end

1-element Vector{Any}:
 CodeInfo(
1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Int64}, svec(Any, Int64), 0, :(:ccall), Vector{Int64}, 3, 3))::Vector{Int64}
│        Base.arrayset(false, %1, 0, 1)::Vector{Int64}
│        Base.arrayset(false, %1, 1, 2)::Vector{Int64}
│        Base.arrayset(false, %1, 2, 3)::Vector{Int64}
└──      return Main.nothing
) => Nothing
```

Further enhancement o optimize cases like above will be based on top of
incoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Feb 22, 2022
@aviatesk @LilithHafner
follow up JuliaLang#43565 (JuliaLang#43755)
19cfd38
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Mar 8, 2022
@aviatesk @LilithHafner
optimizer: compute side-effect-freeness for array allocations (JuliaL…
ae494c8 
…ang#43565)

This would be useful for Julia-level optimizations on arrays.
Initially I want to have this in order to add array primitives support
in EscapeAnalysis.jl, which should help us implement a variety of array
optimizations including dead array allocation elimination, copy-elision
from `Array` to `ImmutableArray` conversion (JuliaLang#42465), etc., but I found
this might be already useful for us since this enables some DCE in very
simple cases like:
```julia
julia> function simple!(x::T) where T
           d = IdDict{T,T}() # dead alloc
           # ... computations that don't use `d` at all
           return nothing
       end
simple! (generic function with 1 method)

julia> @code_typed simple!("foo")
CodeInfo(
1 ─     return Main.nothing
) => Nothing
```

This enhancement is super limited though, e.g. DCE won't happen when
array allocation involves other primitive operations like `arrayset`:
```julia
julia> code_typed() do
           a = Int[0,1,2]
           nothing
       end

1-element Vector{Any}:
 CodeInfo(
1 ─ %1 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Vector{Int64}, svec(Any, Int64), 0, :(:ccall), Vector{Int64}, 3, 3))::Vector{Int64}
│        Base.arrayset(false, %1, 0, 1)::Vector{Int64}
│        Base.arrayset(false, %1, 1, 2)::Vector{Int64}
│        Base.arrayset(false, %1, 2, 3)::Vector{Int64}
└──      return Main.nothing
) => Nothing
```

Further enhancement o optimize cases like above will be based on top of
incoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Mar 8, 2022
@aviatesk @LilithHafner
follow up JuliaLang#43565 (JuliaLang#43755)
9aaa42e
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@vtjnash vtjnash vtjnash left review comments

@KristofferC KristofferC KristofferC left review comments

@Keno Keno Awaiting requested review from Keno

Assignees

No one assigned

Labels

compiler:optimizer Optimization passes (mostly in base/compiler/ssair/)

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@aviatesk @vtjnash @KristofferC