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

Commit665129b

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 bereran after inlining to be used for various local optimizations.
1 parent2118a08 commit665129b

File tree

21 files changed

+5597
-94
lines changed

21 files changed

+5597
-94
lines changed

‎base/boot.jl

Lines changed: 32 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -401,32 +401,38 @@ _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, relocatability::UInt8)=
422-
ccall(:jl_new_codeinst, Ref{CodeInstance}, (Any, Any, Any, Any, Int32, UInt, UInt, UInt8),
423-
mi, rettype, inferred_const, inferred, const_flags, min_world, max_world, relocatability)))
424-
eval(Core, :(Const(@nospecialize(v))=$(Expr(:new,:Const,:v))))
425-
eval(Core, :(PartialStruct(@nospecialize(typ), fields::Array{Any, 1})=$(Expr(:new,:PartialStruct,:typ,:fields))))
426-
eval(Core, :(PartialOpaque(@nospecialize(typ),@nospecialize(env), isva::Bool, parent::MethodInstance, source::Method)=$(Expr(:new,:PartialOpaque,:typ,:env,:isva,:parent,:source))))
427-
eval(Core, :(InterConditional(slot::Int,@nospecialize(vtype),@nospecialize(elsetype))=$(Expr(:new,:InterConditional,:slot,:vtype,:elsetype))))
428-
eval(Core, :(MethodMatch(@nospecialize(spec_types), sparams::SimpleVector, method::Method, fully_covers::Bool)=
429-
$(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+
relocatability::UInt8,@nospecialize(argescapes#=::Union{Nothing,Vector{ArgEscapeInfo}}=#))
426+
returnccall(:jl_new_codeinst, Ref{CodeInstance},
427+
(Any, Any, Any, Any, Int32, UInt, UInt, UInt8, Any),
428+
mi, rettype, inferred_const, inferred, const_flags, min_world, max_world, relocatability, argescapes)
429+
end
430+
Const(@nospecialize(v))=$(Expr(:new,:Const,:v))
431+
PartialStruct(@nospecialize(typ), fields::Array{Any, 1})=$(Expr(:new,:PartialStruct,:typ,:fields))
432+
PartialOpaque(@nospecialize(typ),@nospecialize(env), isva::Bool, parent::MethodInstance, source::Method)=$(Expr(:new,:PartialOpaque,:typ,:env,:isva,:parent,:source))
433+
InterConditional(slot::Int,@nospecialize(vtype),@nospecialize(elsetype))=$(Expr(:new,:InterConditional,:slot,:vtype,:elsetype))
434+
MethodMatch(@nospecialize(spec_types), sparams::SimpleVector, method::Method, fully_covers::Bool)=$(Expr(:new,:MethodMatch,:spec_types,:sparams,:method,:fully_covers))
435+
end)
430436

431437
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)
432438

‎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(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: 76 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,45 @@
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+
# known to be always effect-free (in particular nothrow)
32+
const _PURE_BUILTINS= Any[tuple, svec,===, typeof, nfields]
33+
34+
# known to be effect-free if the are nothrow
35+
const _PURE_OR_ERROR_BUILTINS= [
36+
fieldtype, apply_type, isa, UnionAll,
37+
getfield, arrayref, const_arrayref, arraysize, isdefined, Core.sizeof,
38+
Core.kwfunc, Core.ifelse, Core._typevar, (<:),
39+
]
40+
41+
const TOP_TUPLE=GlobalRef(Core,:tuple)
42+
343
#####################
444
# OptimizationState #
545
#####################
@@ -21,10 +61,10 @@ function push!(et::EdgeTracker, ci::CodeInstance)
2161
push!(et, ci.def)
2262
end
2363

24-
struct InliningState{S<:Union{EdgeTracker, Nothing},T, I<:AbstractInterpreter}
64+
struct InliningState{S<:Union{EdgeTracker, Nothing},MICache, I<:AbstractInterpreter}
2565
params::OptimizationParams
2666
et::S
27-
mi_cache::T
67+
mi_cache::MICache#TODO move this to `OptimizationState` (as used by EscapeAnalysis as well)
2868
interp::I
2969
end
3070

@@ -52,7 +92,34 @@ function inlining_policy(interp::AbstractInterpreter, @nospecialize(src), stmt_f
5292
returnnothing
5393
end
5494

95+
function argextypeend# imported by EscapeAnalysis
96+
function stmt_effect_freeend# imported by EscapeAnalysis
97+
function alloc_array_ndimsend# imported by EscapeAnalysis
5598
include("compiler/ssair/driver.jl")
99+
using.EscapeAnalysis
100+
import.EscapeAnalysis: EscapeState, ArgEscapeInfo
101+
102+
"""
103+
cache_escapes!(caller::InferenceResult, estate::EscapeState)
104+
105+
Transforms escape information of call arguments of `caller`,
106+
and then caches it into a global cache for later interprocedural propagation.
107+
"""
108+
cache_escapes!(caller::InferenceResult, estate::EscapeState)=
109+
caller.argescapes= EscapeAnalysis.to_interprocedural(estate)
110+
111+
functiongetargescapes(mi_cache::MICache)where MICache
112+
returnfunction (linfo::Union{InferenceResult,MethodInstance})
113+
ifisa(linfo, InferenceResult)
114+
argescapes= linfo.argescapes
115+
else
116+
codeinst=get(mi_cache, linfo,nothing)
117+
isa(codeinst, CodeInstance)||returnnothing
118+
argescapes= codeinst.argescapes
119+
end
120+
return argescapes!==nothing? argescapes::Vector{ArgEscapeInfo}:nothing
121+
end
122+
end
56123

57124
mutable struct OptimizationState
58125
linfo::MethodInstance
@@ -121,46 +188,6 @@ function ir_to_codeinf!(opt::OptimizationState)
121188
return src
122189
end
123190

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-
# known to be always effect-free (in particular nothrow)
153-
const _PURE_BUILTINS= Any[tuple, svec,===, typeof, nfields]
154-
155-
# known to be effect-free if the are nothrow
156-
const _PURE_OR_ERROR_BUILTINS= [
157-
fieldtype, apply_type, isa, UnionAll,
158-
getfield, arrayref, const_arrayref, arraysize, isdefined, Core.sizeof,
159-
Core.kwfunc, Core.ifelse, Core._typevar, (<:),
160-
]
161-
162-
const TOP_TUPLE=GlobalRef(Core,:tuple)
163-
164191
#########
165192
# logic #
166193
#########
@@ -511,18 +538,23 @@ end
511538
# run the optimization work
512539
functionoptimize(interp::AbstractInterpreter, opt::OptimizationState,
513540
params::OptimizationParams, caller::InferenceResult)
514-
@timeit"optimizer" ir=run_passes(opt.src, opt)
541+
@timeit"optimizer" ir=run_passes(opt.src, opt, caller)
515542
returnfinish(interp, opt, params, ir, caller)
516543
end
517544

518-
functionrun_passes(ci::CodeInfo, sv::OptimizationState)
545+
functionrun_passes(ci::CodeInfo, sv::OptimizationState, caller::InferenceResult)
519546
@timeit"convert" ir=convert_to_ircode(ci, sv)
520547
@timeit"slot2reg" ir=slot2reg(ir, ci, sv)
521548
#TODO: Domsorting can produce an updated domtree - no need to recompute here
522549
@timeit"compact 1" ir=compact!(ir)
550+
nargs=let def= sv.linfo.def;isa(def, Method)?Int(def.nargs):0;end
551+
getter=getargescapes(sv.inlining.mi_cache)
552+
@timeit"IPO EA" state=analyze_escapes(ir, nargs,false, getter)
553+
cache_escapes!(caller, state)
523554
@timeit"Inlining" ir=ssa_inlining_pass!(ir, ir.linetable, sv.inlining, ci.propagate_inbounds)
524555
# @timeit "verify 2" verify_ir(ir)
525556
@timeit"compact 2" ir=compact!(ir)
557+
@timeit"Local EA" state=analyze_escapes(ir, nargs,true, getter)
526558
@timeit"SROA" ir=sroa_pass!(ir)
527559
@timeit"ADCE" ir=adce_pass!(ir)
528560
@timeit"type lift" ir=type_lift_pass!(ir)

0 commit comments

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