Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

ImmutableArrays#42465

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Closed
ianatol wants to merge58 commits intoJuliaLang:masterfromianatol:kf/immutablearray
Closed

Conversation

ianatol
Copy link
Member

@ianatolianatol commentedOct 2, 2021•
edited
Loading

This PR extends#41777 to provide a dynamically sized immutable arrayImmutableArray.

TheImmutableArray constructor creates an immutable copy of another array, allowing users to get the performance of a mutable array locally, but with the compositionality and safety of an immutable array at the inter-procedural level. In the cases where the compiler can prove (using info from a novelescape analysis pass) that the original array is dead after copying, this benefit comes at no cost to the user.

See the following for an example of a function that utilizes performant, mutating operations while only exposing an immutable array:

function simple()    a = Vector{Float64}(undef, 5)    for i = 1:5        a[i] = i    end    return ImmutableArray(a)end

Using information gathered by the escape analysis pass, the compiler can prove thata is dead after the return, and thus this function is neatly optimized to have the same memory allocation as one that returns a mutable object.

aviatesk, AzamatB, c42f, eliascarv, niklasschmitz, EricForgy, fingolfin, and ParadaCarleton reacted with thumbs up emojieliascarv, AzamatB, and ParadaCarleton reacted with hooray emojisimeonschaub, oscardssmith, longemen3000, ChrisRackauckas, AzamatB, c42f, eliascarv, thazhemadam, mbaz, Tokazama, and 3 more reacted with heart emojieliascarv, AzamatB, and ParadaCarleton reacted with rocket emoji
This rebasesJuliaLang#31630 with several fixed and modifications.AfterJuliaLang#31630, we had originally decided to hold off on saidPR in favor of implementing either more efficient layouts fortuples or some sort of variable-sized struct type. However, inthe two years since, neither of those have happened (I had a goat improving tuples and made some progress, but there is muchstill to be done there). In the meantime, all across the packageecosystem, we've seen an increasing creep of pre-allocation andmutating operations, primarily caused by our lack of sufficientlypowerful immutable array abstractions and array optimizations.This works fine for the individual packages in question, but itcauses a fair bit of trouble when trying to compose these packageswith transformation passes such as AD or domain specific optimizations,since many of those passes do not play well with mutation. Moregenerally, we would like to avoid people needing to pierceabstractions for performance reasons.Given these developments, I think it's getting quite importantthat we start to seriously look at arrays and try to provideperformant and well-optimized arrays in the language. Moreimportantly, I think this is somewhat independent from theactual implementation details. To be sure, it would be niceto move more of the array implementation into Julia by makinguse of one of the abovementioned langugage features, but thatis a bit of an orthogonal concern and not absolutely required.This PR provides an `ImmutableArray` type that is identicalin functionality and implementation to `Array`, except thatit is immutable. Two new intrinsics `Core.arrayfreeze` and`Core.arraythaw` are provided which are semantically copiesand turn a mutable array into an immutable array and viceversa.In the original PR, I additionally provided generic functions`freeze` and `thaw` that would simply forward to theseintrinsics. However, said generic functions have been omittedfrom this PR in favor of simply using constructors to gobetween mutable and immutable arrays at the high level.Generic `freeze`/`thaw` functions can always be added later,once we have a more complete picture of how these functionswould work on non-Array datatypes.Some basic compiler support is provided to elide these copieswhen the compiler can prove that the original object isdead after the copy. For instance, in the following example:```function simple()    a = Vector{Float64}(undef, 5)    for i = 1:5        a[i] = i    end    ImmutableArray(a)end```the compiler will recognize that the array `a` is dead afterits use in `ImmutableArray` and the optimized implementationwill simply rewrite the type tag in the originally allocatedarray to now mark it as immutable. It should be pointed outhowever, that *semantically* there is still no mutation of theoriginal array, this is simply an optimization.At the moment this compiler transform is rather limited, sincethe analysis requires escape information in order to computewhether or not the copy may be elided. However, more completeescape analysis is being worked on at the moment, so hopefullythis analysis should become more powerful in the very near future.I would like to get this cleaned up and merged resonably quickly,and then crowdsource some improvements to the Array APIs moregenerally. There are still a number of APIs that are quite boundto the notion of mutable `Array`s. StaticArrays and other packageshave been inventing conventions for how to generalize those, butwe should form a view in Base what those APIs should look like andharmonize them. Having the `ImmutableArray` in Base should helpwith that.
Comment on lines 1426 to 1430
# Now handle the remaining values
# The typeassert gives inference a helping hand on the element type and dimensionality
# (work-around for #28382)
ElType′ = ElType === Union{} ? Any : ElType <: Type ? Type : ElType
RT = dest isa AbstractArray ? AbstractArray{<:ElType′, ndims(dest)} : Any
Copy link
Member

Choose a reason for hiding this comment

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

Not directly related to this PR, but might be a good opportunity to check whether this still holds true with the recent inference improvements.

@vtjnashvtjnash marked this pull request as draftOctober 2, 2021 17:17
@ianatolianatol requested a review fromvtjnashOctober 6, 2021 15:47
@vtjnashvtjnash removed their request for reviewOctober 7, 2021 17:06
@ianatolianatol requested a review fromvtjnashOctober 7, 2021 22:17
@aviateskaviatesk self-requested a reviewOctober 13, 2021 13:59
@ianatolianatolforce-pushed thekf/immutablearray branch 2 times, most recently from1724ee8 toa164ef4CompareOctober 16, 2021 09:53
@ianatolianatol marked this pull request as ready for reviewOctober 25, 2021 20:14
@ianatolianatol marked this pull request as draftOctober 25, 2021 20:20
@ianatolianatolforce-pushed thekf/immutablearray branch 3 times, most recently frome67ae7c to29681b6CompareOctober 29, 2021 18:40
aviatesk added a commit that referenced this pull requestFeb 3, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will bereran after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 8, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will bereran after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 8, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will bereran after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 9, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will bereran after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 9, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will bereran after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 9, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will bereran after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 10, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 10, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 10, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 10, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 12, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 13, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 14, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 15, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
@ianatolianatol changed the titleImmutableArrays & EscapeAnalysisImmutableArraysFeb 15, 2022
ianatol pushed a commit to ianatol/julia that referenced this pull requestFeb 16, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (JuliaLang#43888),array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit likeJuliaLang#43888,JuliaLang#43909 andJuliaLang#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 16, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 16, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA in this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA in this commit, and then merge thedepending PRs built on top of this commit like#43888,#43909 and#42465This commit simply defines and runs EA inside Julia base compiler andenables the existing test suite with it. In this commit, we just run EAbefore inlining to generate IPO cache. The depending PRs, EA will beinvoked again after inlining to be used for various local optimizations.
aviatesk added a commit that referenced this pull requestFeb 16, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA by this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA to Julia Base by this commit, andthen merge the depending PRs built on top of this commit later.This commit simply defines EA inside Julia base compiler and enables theexisting test suite with it. In this commit we don't run EA at all, andso this commit shouldn't affect Julia-level compilation latency.In the depending PRs, EA will run in two stages:- `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache- `Local EA`: run EA on post-inlining state to generate local escape              information used for various optimizationsIn order to integrate `IPO EA` with our compilation cache system,this commit also implements a new `CodeInstance.argescapes` field thatkeeps the IPO-valid cache generated by `IPO EA`.
aviatesk added a commit that referenced this pull requestFeb 16, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA by this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA to Julia Base by this commit, andthen merge the depending PRs built on top of this commit later.This commit simply defines EA inside Julia base compiler and enables theexisting test suite with it. In this commit we don't run EA at all, andso this commit shouldn't affect Julia-level compilation latency.In the depending PRs, EA will run in two stages:- `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache- `Local EA`: run EA on post-inlining state to generate local escape              information used for various optimizationsIn order to integrate `IPO EA` with our compilation cache system,this commit also implements a new `CodeInstance.argescapes` field thatkeeps the IPO-valid cache generated by `IPO EA`.
JeffBezanson pushed a commit that referenced this pull requestFeb 16, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (#43888),array SROA (#43909), `mutating_arrayfreeze` optimization (#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA by this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA to Julia Base by this commit, andthen merge the depending PRs built on top of this commit later.This commit simply defines EA inside Julia base compiler and enables theexisting test suite with it. In this commit we don't run EA at all, andso this commit shouldn't affect Julia-level compilation latency.In the depending PRs, EA will run in two stages:- `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache- `Local EA`: run EA on post-inlining state to generate local escape              information used for various optimizationsIn order to integrate `IPO EA` with our compilation cache system,this commit also implements a new `CodeInstance.argescapes` field thatkeeps the IPO-valid cache generated by `IPO EA`.
antoine-levitt pushed a commit to antoine-levitt/julia that referenced this pull requestFeb 17, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (JuliaLang#43888),array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA by this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA to Julia Base by this commit, andthen merge the depending PRs built on top of this commit later.This commit simply defines EA inside Julia base compiler and enables theexisting test suite with it. In this commit we don't run EA at all, andso this commit shouldn't affect Julia-level compilation latency.In the depending PRs, EA will run in two stages:- `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache- `Local EA`: run EA on post-inlining state to generate local escape              information used for various optimizationsIn order to integrate `IPO EA` with our compilation cache system,this commit also implements a new `CodeInstance.argescapes` field thatkeeps the IPO-valid cache generated by `IPO EA`.
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull requestFeb 22, 2022
…ang#43565)This would be useful for Julia-level optimizations on arrays.Initially I want to have this in order to add array primitives supportin EscapeAnalysis.jl, which should help us implement a variety of arrayoptimizations including dead array allocation elimination, copy-elisionfrom `Array` to `ImmutableArray` conversion (JuliaLang#42465), etc., but I foundthis might be already useful for us since this enables some DCE in verysimple cases like:```juliajulia> function simple!(x::T) where T           d = IdDict{T,T}() # dead alloc           # ... computations that don't use `d` at all           return nothing       endsimple! (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 whenarray allocation involves other primitive operations like `arrayset`:```juliajulia> code_typed() do           a = Int[0,1,2]           nothing       end1-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 ofincoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull requestFeb 22, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (JuliaLang#43888),array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA by this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA to Julia Base by this commit, andthen merge the depending PRs built on top of this commit later.This commit simply defines EA inside Julia base compiler and enables theexisting test suite with it. In this commit we don't run EA at all, andso this commit shouldn't affect Julia-level compilation latency.In the depending PRs, EA will run in two stages:- `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache- `Local EA`: run EA on post-inlining state to generate local escape              information used for various optimizationsIn order to integrate `IPO EA` with our compilation cache system,this commit also implements a new `CodeInstance.argescapes` field thatkeeps the IPO-valid cache generated by `IPO EA`.
@ianatol
Copy link
MemberAuthor

Superseded by#44381

LilithHafner pushed a commit to LilithHafner/julia that referenced this pull requestMar 8, 2022
…ang#43565)This would be useful for Julia-level optimizations on arrays.Initially I want to have this in order to add array primitives supportin EscapeAnalysis.jl, which should help us implement a variety of arrayoptimizations including dead array allocation elimination, copy-elisionfrom `Array` to `ImmutableArray` conversion (JuliaLang#42465), etc., but I foundthis might be already useful for us since this enables some DCE in verysimple cases like:```juliajulia> function simple!(x::T) where T           d = IdDict{T,T}() # dead alloc           # ... computations that don't use `d` at all           return nothing       endsimple! (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 whenarray allocation involves other primitive operations like `arrayset`:```juliajulia> code_typed() do           a = Int[0,1,2]           nothing       end1-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 ofincoming EA.jl (Julia-level escape analysis) or LLVM-level escape analysis.
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull requestMar 8, 2022
This commit ports [EscapeAnalysis.jl](https://github.com/aviatesk/EscapeAnalysis.jl) into Julia base.You can find the documentation of this escape analysis at [this GitHub page](https://aviatesk.github.io/EscapeAnalysis.jl/dev/)[^1].[^1]: The same documentation will be included into Julia's developer      documentation by this commit.This escape analysis will hopefully be an enabling technology for variousmemory-related optimizations at Julia's high level compilation pipeline.Possible target optimization includes alias aware SROA (JuliaLang#43888),array SROA (JuliaLang#43909), `mutating_arrayfreeze` optimization (JuliaLang#42465),stack allocation of mutables, finalizer elision and so on[^2].[^2]: It would be also interesting if LLVM-level optimizations can consume      IPO information derived by this escape analysis to broaden      optimization possibilities.The primary motivation for porting EA by this PR is to check its impacton latency as well as to get feedbacks from a broader range of developers.The plan is that we first introduce EA to Julia Base by this commit, andthen merge the depending PRs built on top of this commit later.This commit simply defines EA inside Julia base compiler and enables theexisting test suite with it. In this commit we don't run EA at all, andso this commit shouldn't affect Julia-level compilation latency.In the depending PRs, EA will run in two stages:- `IPO EA`: run EA on pre-inlining state to generate IPO-valid cache- `Local EA`: run EA on post-inlining state to generate local escape              information used for various optimizationsIn order to integrate `IPO EA` with our compilation cache system,this commit also implements a new `CodeInstance.argescapes` field thatkeeps the IPO-valid cache generated by `IPO EA`.
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@vchuravyvchuravyvchuravy left review comments

@simeonschaubsimeonschaubsimeonschaub left review comments

@oscardssmithoscardssmithoscardssmith left review comments

@vtjnashvtjnashAwaiting requested review from vtjnash

@aviateskaviateskAwaiting requested review from aviatesk

Assignees
No one assigned
Labels
arrays[a, r, r, a, y, s]compiler:optimizerOptimization passes (mostly in base/compiler/ssair/)
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

7 participants
@ianatol@aviatesk@vchuravy@vtjnash@simeonschaub@oscardssmith@Keno
[8]ページ先頭
©2009-2025 Movatter.jp