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

Commit1070f94

Browse files
committed
optimizer: Julia-level escape analysis
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.
1 parent0bf6ce3 commit1070f94

24 files changed

+5648
-87
lines changed

‎base/boot.jl

Lines changed: 33 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -401,33 +401,39 @@ _new(:QuoteNode, :Any)
401401
_new(:SSAValue,:Int)
402402
_new(:Argument,:Int)
403403
_new(:ReturnNode,:Any)
404-
eval(Core, :(ReturnNode()=$(Expr(:new,:ReturnNode))))# unassigned val indicates unreachable
405-
eval(Core, :(GotoIfNot(@nospecialize(cond), dest::Int)=$(Expr(:new,:GotoIfNot,:cond,:dest))))
406-
eval(Core, :(LineNumberNode(l::Int)=$(Expr(:new,:LineNumberNode,:l,nothing))))
407-
eval(Core, :(LineNumberNode(l::Int,@nospecialize(f))=$(Expr(:new,:LineNumberNode,:l,:f))))
408-
LineNumberNode(l::Int, f::String)=LineNumberNode(l,Symbol(f))
409-
eval(Core, :(GlobalRef(m::Module, s::Symbol)=$(Expr(:new,:GlobalRef,:m,:s))))
410-
eval(Core, :(SlotNumber(n::Int)=$(Expr(:new,:SlotNumber,:n))))
411-
eval(Core, :(TypedSlot(n::Int,@nospecialize(t))=$(Expr(:new,:TypedSlot,:n,:t))))
412-
eval(Core, :(PhiNode(edges::Array{Int32, 1}, values::Array{Any, 1})=$(Expr(:new,:PhiNode,:edges,:values))))
413-
eval(Core, :(PiNode(val, typ)=$(Expr(:new,:PiNode,:val,:typ))))
414-
eval(Core, :(PhiCNode(values::Array{Any, 1})=$(Expr(:new,:PhiCNode,:values))))
415-
eval(Core, :(UpsilonNode(val)=$(Expr(:new,:UpsilonNode,:val))))
416-
eval(Core, :(UpsilonNode()=$(Expr(:new,:UpsilonNode))))
417-
eval(Core, :(LineInfoNode(mod::Module,@nospecialize(method), file::Symbol, line::Int, inlined_at::Int)=
418-
$(Expr(:new,:LineInfoNode,:mod,:method,:file,:line,:inlined_at))))
419-
eval(Core, :(CodeInstance(mi::MethodInstance,@nospecialize(rettype),@nospecialize(inferred_const),
420-
@nospecialize(inferred), const_flags::Int32,
421-
min_world::UInt, max_world::UInt, ipo_effects::UInt8, effects::UInt8,
422-
relocatability::UInt8)=
423-
ccall(:jl_new_codeinst, Ref{CodeInstance}, (Any, Any, Any, Any, Int32, UInt, UInt, UInt8, UInt8, UInt8),
424-
mi, rettype, inferred_const, inferred, const_flags, min_world, max_world, ipo_effects, effects, relocatability)))
425-
eval(Core, :(Const(@nospecialize(v))=$(Expr(:new,:Const,:v))))
426-
eval(Core, :(PartialStruct(@nospecialize(typ), fields::Array{Any, 1})=$(Expr(:new,:PartialStruct,:typ,:fields))))
427-
eval(Core, :(PartialOpaque(@nospecialize(typ),@nospecialize(env), isva::Bool, parent::MethodInstance, source::Method)=$(Expr(:new,:PartialOpaque,:typ,:env,:isva,:parent,:source))))
428-
eval(Core, :(InterConditional(slot::Int,@nospecialize(vtype),@nospecialize(elsetype))=$(Expr(:new,:InterConditional,:slot,:vtype,:elsetype))))
429-
eval(Core, :(MethodMatch(@nospecialize(spec_types), sparams::SimpleVector, method::Method, fully_covers::Bool)=
430-
$(Expr(:new,:MethodMatch,:spec_types,:sparams,:method,:fully_covers))))
404+
eval(Core,quote
405+
ReturnNode()=$(Expr(:new,:ReturnNode))# unassigned val indicates unreachable
406+
GotoIfNot(@nospecialize(cond), dest::Int)=$(Expr(:new,:GotoIfNot,:cond,:dest))
407+
LineNumberNode(l::Int)=$(Expr(:new,:LineNumberNode,:l,nothing))
408+
functionLineNumberNode(l::Int,@nospecialize(f))
409+
isa(f, String)&& (f=Symbol(f))
410+
return$(Expr(:new,:LineNumberNode,:l,:f))
411+
end
412+
LineInfoNode(mod::Module,@nospecialize(method), file::Symbol, line::Int, inlined_at::Int)=
413+
$(Expr(:new,:LineInfoNode,:mod,:method,:file,:line,:inlined_at))
414+
GlobalRef(m::Module, s::Symbol)=$(Expr(:new,:GlobalRef,:m,:s))
415+
SlotNumber(n::Int)=$(Expr(:new,:SlotNumber,:n))
416+
TypedSlot(n::Int,@nospecialize(t))=$(Expr(:new,:TypedSlot,:n,:t))
417+
PhiNode(edges::Array{Int32, 1}, values::Array{Any, 1})=$(Expr(:new,:PhiNode,:edges,:values))
418+
PiNode(@nospecialize(val),@nospecialize(typ))=$(Expr(:new,:PiNode,:val,:typ))
419+
PhiCNode(values::Array{Any, 1})=$(Expr(:new,:PhiCNode,:values))
420+
UpsilonNode(@nospecialize(val))=$(Expr(:new,:UpsilonNode,:val))
421+
UpsilonNode()=$(Expr(:new,:UpsilonNode))
422+
functionCodeInstance(
423+
mi::MethodInstance,@nospecialize(rettype),@nospecialize(inferred_const),
424+
@nospecialize(inferred), const_flags::Int32, min_world::UInt, max_world::UInt,
425+
ipo_effects::UInt8, effects::UInt8,@nospecialize(argescapes#=::Union{Nothing,Vector{ArgEscapeInfo}}=#),
426+
relocatability::UInt8)
427+
returnccall(:jl_new_codeinst, Ref{CodeInstance},
428+
(Any, Any, Any, Any, Int32, UInt, UInt, UInt8, UInt8, Any, UInt8),
429+
mi, rettype, inferred_const, inferred, const_flags, min_world, max_world, ipo_effects, effects, argescapes, relocatability)
430+
end
431+
Const(@nospecialize(v))=$(Expr(:new,:Const,:v))
432+
PartialStruct(@nospecialize(typ), fields::Array{Any, 1})=$(Expr(:new,:PartialStruct,:typ,:fields))
433+
PartialOpaque(@nospecialize(typ),@nospecialize(env), isva::Bool, parent::MethodInstance, source::Method)=$(Expr(:new,:PartialOpaque,:typ,:env,:isva,:parent,:source))
434+
InterConditional(slot::Int,@nospecialize(vtype),@nospecialize(elsetype))=$(Expr(:new,:InterConditional,:slot,:vtype,:elsetype))
435+
MethodMatch(@nospecialize(spec_types), sparams::SimpleVector, method::Method, fully_covers::Bool)=$(Expr(:new,:MethodMatch,:spec_types,:sparams,:method,:fully_covers))
436+
end)
431437

432438
Module(name::Symbol=:anonymous, std_imports::Bool=true, default_names::Bool=true)=ccall(:jl_f_new_module, Ref{Module}, (Any, Bool, Bool), name, std_imports, default_names)
433439

‎base/compiler/bootstrap.jl

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,10 +11,11 @@ let
1111
world=get_world_counter()
1212
interp=NativeInterpreter(world)
1313

14+
analyze_escapes_tt= Tuple{typeof(analyze_escapes), IRCode, Int, Bool,typeof(get_escape_cache(code_cache(interp)))}
1415
fs= Any[
1516
# we first create caches for the optimizer, because they contain many loop constructions
1617
# and they're better to not run in interpreter even during bootstrapping
17-
run_passes,
18+
analyze_escapes_tt,run_passes,
1819
# then we create caches for inference entries
1920
typeinf_ext, typeinf, typeinf_edge,
2021
]
@@ -32,7 +33,12 @@ let
3233
end
3334
starttime=time()
3435
for fin fs
35-
for min_methods_by_ftype(Tuple{typeof(f), Vararg{Any}},10,typemax(UInt))
36+
ifisa(f, DataType)&& f.name===typename(Tuple)
37+
tt= f
38+
else
39+
tt= Tuple{typeof(f), Vararg{Any}}
40+
end
41+
for min_methods_by_ftype(tt,10,typemax(UInt))
3642
# remove any TypeVars from the intersection
3743
typ= Any[m.spec_types.parameters...]
3844
for i=1:length(typ)

‎base/compiler/compiler.jl

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,8 @@ ntuple(f, n) = (Any[f(i) for i = 1:n]...,)
9797

9898
# core docsystem
9999
include("docs/core.jl")
100+
import Core.Compiler.CoreDocs
101+
Core.atdoc!(CoreDocs.docm)
100102

101103
# sorting
102104
function sortend

‎base/compiler/optimize.jl

Lines changed: 69 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,35 @@
11
# This file is a part of Julia. License is MIT: https://julialang.org/license
22

3+
#############
4+
# constants #
5+
#############
6+
7+
# The slot has uses that are not statically dominated by any assignment
8+
# This is implied by `SLOT_USEDUNDEF`.
9+
# If this is not set, all the uses are (statically) dominated by the defs.
10+
# In particular, if a slot has `AssignedOnce && !StaticUndef`, it is an SSA.
11+
const SLOT_STATICUNDEF=1# slot might be used before it is defined (structurally)
12+
const SLOT_ASSIGNEDONCE=16# slot is assigned to only once
13+
const SLOT_USEDUNDEF=32# slot has uses that might raise UndefVarError
14+
# const SLOT_CALLED = 64
15+
16+
# NOTE make sure to sync the flag definitions below with julia.h and `jl_code_info_set_ir` in method.c
17+
18+
const IR_FLAG_NULL=0x00
19+
# This statement is marked as @inbounds by user.
20+
# Ff replaced by inlining, any contained boundschecks may be removed.
21+
const IR_FLAG_INBOUNDS=0x01<<0
22+
# This statement is marked as @inline by user
23+
const IR_FLAG_INLINE=0x01<<1
24+
# This statement is marked as @noinline by user
25+
const IR_FLAG_NOINLINE=0x01<<2
26+
const IR_FLAG_THROW_BLOCK=0x01<<3
27+
# This statement may be removed if its result is unused. In particular it must
28+
# thus be both pure and effect free.
29+
const IR_FLAG_EFFECT_FREE=0x01<<4
30+
31+
const TOP_TUPLE=GlobalRef(Core,:tuple)
32+
333
#####################
434
# OptimizationState #
535
#####################
@@ -21,10 +51,10 @@ function push!(et::EdgeTracker, ci::CodeInstance)
2151
push!(et, ci.def)
2252
end
2353

24-
struct InliningState{S<:Union{EdgeTracker, Nothing},T, I<:AbstractInterpreter}
54+
struct InliningState{S<:Union{EdgeTracker, Nothing},MICache, I<:AbstractInterpreter}
2555
params::OptimizationParams
2656
et::S
27-
mi_cache::T
57+
mi_cache::MICache#TODO move this to `OptimizationState` (as used by EscapeAnalysis as well)
2858
interp::I
2959
end
3060

@@ -52,7 +82,34 @@ function inlining_policy(interp::AbstractInterpreter, @nospecialize(src), stmt_f
5282
returnnothing
5383
end
5484

85+
function argextypeend# imported by EscapeAnalysis
86+
function stmt_effect_freeend# imported by EscapeAnalysis
87+
function alloc_array_ndimsend# imported by EscapeAnalysis
5588
include("compiler/ssair/driver.jl")
89+
using.EscapeAnalysis
90+
import.EscapeAnalysis: EscapeState, ArgEscapeCache, is_ipo_profitable
91+
92+
"""
93+
cache_escapes!(caller::InferenceResult, estate::EscapeState)
94+
95+
Transforms escape information of call arguments of `caller`,
96+
and then caches it into a global cache for later interprocedural propagation.
97+
"""
98+
cache_escapes!(caller::InferenceResult, estate::EscapeState)=
99+
caller.argescapes=ArgEscapeCache(estate)
100+
101+
functionget_escape_cache(mi_cache::MICache)where MICache
102+
returnfunction (linfo::Union{InferenceResult,MethodInstance})
103+
ifisa(linfo, InferenceResult)
104+
argescapes= linfo.argescapes
105+
else
106+
codeinst=get(mi_cache, linfo,nothing)
107+
isa(codeinst, CodeInstance)||returnnothing
108+
argescapes= codeinst.argescapes
109+
end
110+
return argescapes!==nothing? argescapes::ArgEscapeCache:nothing
111+
end
112+
end
56113

57114
mutable struct OptimizationState
58115
linfo::MethodInstance
@@ -121,36 +178,6 @@ function ir_to_codeinf!(opt::OptimizationState)
121178
return src
122179
end
123180

124-
#############
125-
# constants #
126-
#############
127-
128-
# The slot has uses that are not statically dominated by any assignment
129-
# This is implied by `SLOT_USEDUNDEF`.
130-
# If this is not set, all the uses are (statically) dominated by the defs.
131-
# In particular, if a slot has `AssignedOnce && !StaticUndef`, it is an SSA.
132-
const SLOT_STATICUNDEF=1# slot might be used before it is defined (structurally)
133-
const SLOT_ASSIGNEDONCE=16# slot is assigned to only once
134-
const SLOT_USEDUNDEF=32# slot has uses that might raise UndefVarError
135-
# const SLOT_CALLED = 64
136-
137-
# NOTE make sure to sync the flag definitions below with julia.h and `jl_code_info_set_ir` in method.c
138-
139-
const IR_FLAG_NULL=0x00
140-
# This statement is marked as @inbounds by user.
141-
# Ff replaced by inlining, any contained boundschecks may be removed.
142-
const IR_FLAG_INBOUNDS=0x01<<0
143-
# This statement is marked as @inline by user
144-
const IR_FLAG_INLINE=0x01<<1
145-
# This statement is marked as @noinline by user
146-
const IR_FLAG_NOINLINE=0x01<<2
147-
const IR_FLAG_THROW_BLOCK=0x01<<3
148-
# This statement may be removed if its result is unused. In particular it must
149-
# thus be both pure and effect free.
150-
const IR_FLAG_EFFECT_FREE=0x01<<4
151-
152-
const TOP_TUPLE=GlobalRef(Core,:tuple)
153-
154181
#########
155182
# logic #
156183
#########
@@ -503,15 +530,23 @@ end
503530
# run the optimization work
504531
functionoptimize(interp::AbstractInterpreter, opt::OptimizationState,
505532
params::OptimizationParams, caller::InferenceResult)
506-
@timeit"optimizer" ir=run_passes(opt.src, opt)
533+
@timeit"optimizer" ir=run_passes(opt.src, opt, caller)
507534
returnfinish(interp, opt, params, ir, caller)
508535
end
509536

510-
functionrun_passes(ci::CodeInfo, sv::OptimizationState)
537+
functionrun_passes(ci::CodeInfo, sv::OptimizationState, caller::InferenceResult)
511538
@timeit"convert" ir=convert_to_ircode(ci, sv)
512539
@timeit"slot2reg" ir=slot2reg(ir, ci, sv)
513540
#TODO: Domsorting can produce an updated domtree - no need to recompute here
514541
@timeit"compact 1" ir=compact!(ir)
542+
nargs=let def= sv.linfo.def;isa(def, Method)?Int(def.nargs):0;end
543+
get_escape_cache= (@__MODULE__).get_escape_cache(sv.inlining.mi_cache)
544+
ifis_ipo_profitable(ir, nargs)
545+
@timeit"IPO EA"begin
546+
state=analyze_escapes(ir, nargs,false, get_escape_cache)
547+
cache_escapes!(caller, state)
548+
end
549+
end
515550
@timeit"Inlining" ir=ssa_inlining_pass!(ir, ir.linetable, sv.inlining, ci.propagate_inbounds)
516551
# @timeit "verify 2" verify_ir(ir)
517552
@timeit"compact 2" ir=compact!(ir)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp