optimizer: enable SROA of mutable φ-nodes#43505
Closed
aviatesk wants to merge 1 commit intoavi/multisroafrom
Closed
optimizer: enable SROA of mutable φ-nodes#43505aviatesk wants to merge 1 commit intoavi/multisroafrom
aviatesk wants to merge 1 commit intoavi/multisroafrom
Conversation
dec65e1 to
738df81
Compare
73fbd3d to
1b8be01
Compare
738df81 to
dd6d086
Compare
1b8be01 to
d2cf634
Compare
dd6d086 to
250059f
Compare
c19c4e4 to
2ddf09f
Compare
0908ab4 to
e1e502e
Compare
2ddf09f to
29fd2ac
Compare
e1e502e to
a9c6daf
Compare
This commit allows elimination of mutable φ-node (and its predecessor mutables allocations).
As an contrived example, it allows this `mutable_ϕ_elim(::String, ::Vector{String})`
to run without any allocations at all:
```julia
function mutable_ϕ_elim(x, xs)
r = Ref(x)
for x in xs
r = Ref(x)
end
return r[]
end
let xs = String[string(gensym()) for _ in 1:100]
mutable_ϕ_elim("init", xs)
@test @allocated(mutable_ϕ_elim("init", xs)) == 0
end
```
This mutable ϕ-node elimination is still limited though.
Most notably, the current implementation doesn't work if a mutable
allocation forms multiple ϕ-nodes, since we check allocation eliminability
(i.e. escapability) by counting usages counts and thus it's hard to
reason about multiple ϕ-nodes at a time.
For example, currently mutable allocations involved in cases like below
will still not be eliminated:
```julia
code_typed((Bool,String,String),) do cond, x, y
if cond
ϕ2 = ϕ1 = Ref(x)
else
ϕ2 = ϕ1 = Ref(y)
end
ϕ1[], ϕ2[]
end
\# more realistic example
mutable struct Point{T}
x::T
y::T
end
add(a::Point, b::Point) = Point(a.x + b.x, a.y + b.y)
function compute(a::Point{ComplexF64}, b::Point{ComplexF64})
for i in 0:(100000000-1)
a = add(add(a, b), b)
end
a.x, a.y
end
```
I'd say this limitation should be addressed by first introducing a better
abstraction for reasoning escape information. More specifically, I'd like
introduce EscapeAnalysis.jl into Julia base first, and then gradually
adapt it to improve our SROA pass, since EA will allow us to reason about
all escape information imposed on whatever object more easily and should
help us get rid of the complexities of our current SROA implementation.
For now, I'd like to get in this enhancement even though it has the
limitation elaborated above, as far as this commit doesn't introduce
latency problem (which is unlikely).
29fd2ac to
bf97c29
Compare
Member
|
@aviatesk what's the status of this PR? It's 3 years old and actually targets another branch of your, |
Member
Author
|
I think this should be closed now. We need to re-implement this on top of #56849. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This commit allows elimination of mutable φ-node (and its predecessor mutable allocations).
As an contrived example, it allows this
mutable_ϕ_elim(::String, ::Vector{String})to run without any allocations at all:
This mutable ϕ-node elimination is still limited though.
Most notably, the current implementation doesn't work if a mutable
allocation forms multiple ϕ-nodes, since we check allocation eliminability
(i.e. escapability) by counting usages by def-chain walking and thus
it's hard to reason about multiple ϕ-nodes at a time.
For example, currently mutable allocations involved in cases like below
will still not be eliminated:
I'd say this limitation should be addressed by first introducing a better
abstraction for reasoning escape information. More specifically, I'd like
introduce EscapeAnalysis.jl into Julia base first, and then gradually
adapt it to improve our SROA pass, since EA will allow us to reason about
all escape information imposed on whatever object more easily and should
help us get rid of the complexities of our current SROA implementation.
For now, I'd like to get in this enhancement even though it has the
limitation elaborated above, as far as this commit doesn't introduce
latency problem (which I believe is unlikely).