/
EscapeAnalysis.jl
1913 lines (1776 loc) · 72.5 KB
/
EscapeAnalysis.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
baremodule EscapeAnalysis
export
analyze_escapes,
getaliases,
isaliased,
has_no_escape,
has_arg_escape,
has_return_escape,
has_thrown_escape,
has_all_escape
const _TOP_MOD = ccall(:jl_base_relative_to, Any, (Any,), EscapeAnalysis)::Module
# imports
import ._TOP_MOD: ==, getindex, setindex!
# usings
import Core:
MethodInstance, Const, Argument, SSAValue, PiNode, PhiNode, UpsilonNode, PhiCNode,
ReturnNode, GotoNode, GotoIfNot, SimpleVector, MethodMatch, CodeInstance,
sizeof, ifelse, arrayset, arrayref, arraysize
import ._TOP_MOD: # Base definitions
@__MODULE__, @eval, @assert, @specialize, @nospecialize, @inbounds, @inline, @noinline,
@label, @goto, !, !==, !=, ≠, +, -, *, ≤, <, ≥, >, &, |, <<, error, missing, copy,
Vector, BitSet, IdDict, IdSet, UnitRange, Csize_t, Callable, ∪, ⊆, ∩, :, ∈, ∉, =>,
in, length, get, first, last, haskey, keys, get!, isempty, isassigned,
pop!, push!, pushfirst!, empty!, delete!, max, min, enumerate, unwrap_unionall,
ismutabletype
import Core.Compiler: # Core.Compiler specific definitions
Bottom, InferenceResult, IRCode, IR_FLAG_EFFECT_FREE,
isbitstype, isexpr, is_meta_expr_head, println, widenconst, argextype, singleton_type,
fieldcount_noerror, try_compute_field, try_compute_fieldidx, hasintersect, ⊑,
intrinsic_nothrow, array_builtin_common_typecheck, arrayset_typecheck,
setfield!_nothrow, alloc_array_ndims, stmt_effect_free, check_effect_free!
include(x) = _TOP_MOD.include(@__MODULE__, x)
if _TOP_MOD === Core.Compiler
include("compiler/ssair/EscapeAnalysis/disjoint_set.jl")
else
include("disjoint_set.jl")
end
const AInfo = IdSet{Any}
const LivenessSet = BitSet
"""
x::EscapeInfo
A lattice for escape information, which holds the following properties:
- `x.Analyzed::Bool`: not formally part of the lattice, only indicates `x` has not been analyzed or not
- `x.ReturnEscape::Bool`: indicates `x` can escape to the caller via return
- `x.ThrownEscape::BitSet`: records SSA statement numbers where `x` can be thrown as exception:
* `isempty(x.ThrownEscape)`: `x` will never be thrown in this call frame (the bottom)
* `pc ∈ x.ThrownEscape`: `x` may be thrown at the SSA statement at `pc`
* `-1 ∈ x.ThrownEscape`: `x` may be thrown at arbitrary points of this call frame (the top)
This information will be used by `escape_exception!` to propagate potential escapes via exception.
- `x.AliasInfo::Union{Bool,IndexableFields,IndexableElements,Unindexable}`: maintains all possible values
that can be aliased to fields or array elements of `x`:
* `x.AliasInfo === false` indicates the fields/elements of `x` aren't analyzed yet
* `x.AliasInfo === true` indicates the fields/elements of `x` can't be analyzed,
e.g. the type of `x` is not known or is not concrete and thus its fields/elements
can't be known precisely
* `x.AliasInfo::IndexableFields` records all the possible values that can be aliased to fields of object `x` with precise index information
* `x.AliasInfo::IndexableElements` records all the possible values that can be aliased to elements of array `x` with precise index information
* `x.AliasInfo::Unindexable` records all the possible values that can be aliased to fields/elements of `x` without precise index information
- `x.Liveness::BitSet`: records SSA statement numbers where `x` should be live, e.g.
to be used as a call argument, to be returned to a caller, or preserved for `:foreigncall`:
* `isempty(x.Liveness)`: `x` is never be used in this call frame (the bottom)
* `0 ∈ x.Liveness` also has the special meaning that it's a call argument of the currently
analyzed call frame (and thus it's visible from the caller immediately).
* `pc ∈ x.Liveness`: `x` may be used at the SSA statement at `pc`
* `-1 ∈ x.Liveness`: `x` may be used at arbitrary points of this call frame (the top)
There are utility constructors to create common `EscapeInfo`s, e.g.,
- `NoEscape()`: the bottom(-like) element of this lattice, meaning it won't escape to anywhere
- `AllEscape()`: the topmost element of this lattice, meaning it will escape to everywhere
`analyze_escapes` will transition these elements from the bottom to the top,
in the same direction as Julia's native type inference routine.
An abstract state will be initialized with the bottom(-like) elements:
- the call arguments are initialized as `ArgEscape()`, whose `Liveness` property includes `0`
to indicate that it is passed as a call argument and visible from a caller immediately
- the other states are initialized as `NotAnalyzed()`, which is a special lattice element that
is slightly lower than `NoEscape`, but at the same time doesn't represent any meaning
other than it's not analyzed yet (thus it's not formally part of the lattice)
"""
struct EscapeInfo
Analyzed::Bool
ReturnEscape::Bool
ThrownEscape::LivenessSet
AliasInfo #::Union{IndexableFields,IndexableElements,Unindexable,Bool}
Liveness::LivenessSet
function EscapeInfo(
Analyzed::Bool,
ReturnEscape::Bool,
ThrownEscape::LivenessSet,
AliasInfo#=::Union{IndexableFields,IndexableElements,Unindexable,Bool}=#,
Liveness::LivenessSet,
)
@nospecialize AliasInfo
return new(
Analyzed,
ReturnEscape,
ThrownEscape,
AliasInfo,
Liveness,
)
end
function EscapeInfo(
x::EscapeInfo,
# non-concrete fields should be passed as default arguments
# in order to avoid allocating non-concrete `NamedTuple`s
AliasInfo#=::Union{IndexableFields,IndexableElements,Unindexable,Bool}=# = x.AliasInfo;
Analyzed::Bool = x.Analyzed,
ReturnEscape::Bool = x.ReturnEscape,
ThrownEscape::LivenessSet = x.ThrownEscape,
Liveness::LivenessSet = x.Liveness,
)
@nospecialize AliasInfo
return new(
Analyzed,
ReturnEscape,
ThrownEscape,
AliasInfo,
Liveness,
)
end
end
# precomputed default values in order to eliminate computations at each callsite
const BOT_THROWN_ESCAPE = LivenessSet()
# NOTE the lattice operations should try to avoid actual set computations on this top value,
# and e.g. LivenessSet(0:1000000) should also work without incurring excessive computations
const TOP_THROWN_ESCAPE = LivenessSet(-1)
const BOT_LIVENESS = LivenessSet()
# NOTE the lattice operations should try to avoid actual set computations on this top value,
# and e.g. LivenessSet(0:1000000) should also work without incurring excessive computations
const TOP_LIVENESS = LivenessSet(-1:0)
const ARG_LIVENESS = LivenessSet(0)
# the constructors
NotAnalyzed() = EscapeInfo(false, false, BOT_THROWN_ESCAPE, false, BOT_LIVENESS) # not formally part of the lattice
NoEscape() = EscapeInfo(true, false, BOT_THROWN_ESCAPE, false, BOT_LIVENESS)
ArgEscape() = EscapeInfo(true, false, BOT_THROWN_ESCAPE, true, ARG_LIVENESS)
ReturnEscape(pc::Int) = EscapeInfo(true, true, BOT_THROWN_ESCAPE, false, LivenessSet(pc))
AllReturnEscape() = EscapeInfo(true, true, BOT_THROWN_ESCAPE, false, TOP_LIVENESS)
ThrownEscape(pc::Int) = EscapeInfo(true, false, LivenessSet(pc), false, BOT_LIVENESS)
AllEscape() = EscapeInfo(true, true, TOP_THROWN_ESCAPE, true, TOP_LIVENESS)
const ⊥, ⊤ = NotAnalyzed(), AllEscape()
# Convenience names for some ⊑ₑ queries
has_no_escape(x::EscapeInfo) = !x.ReturnEscape && isempty(x.ThrownEscape) && 0 ∉ x.Liveness
has_arg_escape(x::EscapeInfo) = 0 in x.Liveness
has_return_escape(x::EscapeInfo) = x.ReturnEscape
has_return_escape(x::EscapeInfo, pc::Int) = x.ReturnEscape && (-1 ∈ x.Liveness || pc in x.Liveness)
has_thrown_escape(x::EscapeInfo) = !isempty(x.ThrownEscape)
has_thrown_escape(x::EscapeInfo, pc::Int) = -1 ∈ x.ThrownEscape || pc in x.ThrownEscape
has_all_escape(x::EscapeInfo) = ⊤ ⊑ₑ x
# utility lattice constructors
ignore_argescape(x::EscapeInfo) = EscapeInfo(x; Liveness=delete!(copy(x.Liveness), 0))
ignore_thrownescapes(x::EscapeInfo) = EscapeInfo(x; ThrownEscape=BOT_THROWN_ESCAPE)
ignore_aliasinfo(x::EscapeInfo) = EscapeInfo(x, false)
ignore_liveness(x::EscapeInfo) = EscapeInfo(x; Liveness=BOT_LIVENESS)
# AliasInfo
struct IndexableFields
infos::Vector{AInfo}
end
struct IndexableElements
infos::IdDict{Int,AInfo}
end
struct Unindexable
info::AInfo
end
IndexableFields(nflds::Int) = IndexableFields(AInfo[AInfo() for _ in 1:nflds])
Unindexable() = Unindexable(AInfo())
merge_to_unindexable(AliasInfo::IndexableFields) = Unindexable(merge_to_unindexable(AliasInfo.infos))
merge_to_unindexable(AliasInfo::Unindexable, AliasInfos::IndexableFields) = Unindexable(merge_to_unindexable(AliasInfo.info, AliasInfos.infos))
merge_to_unindexable(infos::Vector{AInfo}) = merge_to_unindexable(AInfo(), infos)
function merge_to_unindexable(info::AInfo, infos::Vector{AInfo})
for i = 1:length(infos)
info = info ∪ infos[i]
end
return info
end
merge_to_unindexable(AliasInfo::IndexableElements) = Unindexable(merge_to_unindexable(AliasInfo.infos))
merge_to_unindexable(AliasInfo::Unindexable, AliasInfos::IndexableElements) = Unindexable(merge_to_unindexable(AliasInfo.info, AliasInfos.infos))
merge_to_unindexable(infos::IdDict{Int,AInfo}) = merge_to_unindexable(AInfo(), infos)
function merge_to_unindexable(info::AInfo, infos::IdDict{Int,AInfo})
for idx in keys(infos)
info = info ∪ infos[idx]
end
return info
end
# we need to make sure this `==` operator corresponds to lattice equality rather than object equality,
# otherwise `propagate_changes` can't detect the convergence
x::EscapeInfo == y::EscapeInfo = begin
# fast pass: better to avoid top comparison
x === y && return true
x.Analyzed === y.Analyzed || return false
x.ReturnEscape === y.ReturnEscape || return false
xt, yt = x.ThrownEscape, y.ThrownEscape
if xt === TOP_THROWN_ESCAPE
yt === TOP_THROWN_ESCAPE || return false
elseif yt === TOP_THROWN_ESCAPE
return false # x.ThrownEscape === TOP_THROWN_ESCAPE
else
xt == yt || return false
end
xa, ya = x.AliasInfo, y.AliasInfo
if isa(xa, Bool)
xa === ya || return false
elseif isa(xa, IndexableFields)
isa(ya, IndexableFields) || return false
xa.infos == ya.infos || return false
elseif isa(xa, IndexableElements)
isa(ya, IndexableElements) || return false
xa.infos == ya.infos || return false
else
xa = xa::Unindexable
isa(ya, Unindexable) || return false
xa.info == ya.info || return false
end
xl, yl = x.Liveness, y.Liveness
if xl === TOP_LIVENESS
yl === TOP_LIVENESS || return false
elseif yl === TOP_LIVENESS
return false # x.Liveness === TOP_LIVENESS
else
xl == yl || return false
end
return true
end
"""
x::EscapeInfo ⊑ₑ y::EscapeInfo -> Bool
The non-strict partial order over [`EscapeInfo`](@ref).
"""
x::EscapeInfo ⊑ₑ y::EscapeInfo = begin
# fast pass: better to avoid top comparison
if y === ⊤
return true
elseif x === ⊤
return false # return y === ⊤
elseif x === ⊥
return true
elseif y === ⊥
return false # return x === ⊥
end
x.Analyzed ≤ y.Analyzed || return false
x.ReturnEscape ≤ y.ReturnEscape || return false
xt, yt = x.ThrownEscape, y.ThrownEscape
if xt === TOP_THROWN_ESCAPE
yt !== TOP_THROWN_ESCAPE && return false
elseif yt !== TOP_THROWN_ESCAPE
xt ⊆ yt || return false
end
xa, ya = x.AliasInfo, y.AliasInfo
if isa(xa, Bool)
xa && ya !== true && return false
elseif isa(xa, IndexableFields)
if isa(ya, IndexableFields)
xinfos, yinfos = xa.infos, ya.infos
xn, yn = length(xinfos), length(yinfos)
xn > yn && return false
for i in 1:xn
xinfos[i] ⊆ yinfos[i] || return false
end
elseif isa(ya, IndexableElements)
return false
elseif isa(ya, Unindexable)
xinfos, yinfo = xa.infos, ya.info
for i = length(xinfos)
xinfos[i] ⊆ yinfo || return false
end
else
ya === true || return false
end
elseif isa(xa, IndexableElements)
if isa(ya, IndexableElements)
xinfos, yinfos = xa.infos, ya.infos
keys(xinfos) ⊆ keys(yinfos) || return false
for idx in keys(xinfos)
xinfos[idx] ⊆ yinfos[idx] || return false
end
elseif isa(ya, IndexableFields)
return false
elseif isa(ya, Unindexable)
xinfos, yinfo = xa.infos, ya.info
for idx in keys(xinfos)
xinfos[idx] ⊆ yinfo || return false
end
else
ya === true || return false
end
else
xa = xa::Unindexable
if isa(ya, Unindexable)
xinfo, yinfo = xa.info, ya.info
xinfo ⊆ yinfo || return false
else
ya === true || return false
end
end
xl, yl = x.Liveness, y.Liveness
if xl === TOP_LIVENESS
yl !== TOP_LIVENESS && return false
elseif yl !== TOP_LIVENESS
xl ⊆ yl || return false
end
return true
end
"""
x::EscapeInfo ⊏ₑ y::EscapeInfo -> Bool
The strict partial order over [`EscapeInfo`](@ref).
This is defined as the irreflexive kernel of `⊏ₑ`.
"""
x::EscapeInfo ⊏ₑ y::EscapeInfo = x ⊑ₑ y && !(y ⊑ₑ x)
"""
x::EscapeInfo ⋤ₑ y::EscapeInfo -> Bool
This order could be used as a slightly more efficient version of the strict order `⊏ₑ`,
where we can safely assume `x ⊑ₑ y` holds.
"""
x::EscapeInfo ⋤ₑ y::EscapeInfo = !(y ⊑ₑ x)
"""
x::EscapeInfo ⊔ₑ y::EscapeInfo -> EscapeInfo
Computes the join of `x` and `y` in the partial order defined by [`EscapeInfo`](@ref).
"""
x::EscapeInfo ⊔ₑ y::EscapeInfo = begin
# fast pass: better to avoid top join
if x === ⊤ || y === ⊤
return ⊤
elseif x === ⊥
return y
elseif y === ⊥
return x
end
xt, yt = x.ThrownEscape, y.ThrownEscape
if xt === TOP_THROWN_ESCAPE || yt === TOP_THROWN_ESCAPE
ThrownEscape = TOP_THROWN_ESCAPE
elseif xt === BOT_THROWN_ESCAPE
ThrownEscape = yt
elseif yt === BOT_THROWN_ESCAPE
ThrownEscape = xt
else
ThrownEscape = xt ∪ yt
end
AliasInfo = merge_alias_info(x.AliasInfo, y.AliasInfo)
xl, yl = x.Liveness, y.Liveness
if xl === TOP_LIVENESS || yl === TOP_LIVENESS
Liveness = TOP_LIVENESS
elseif xl === BOT_LIVENESS
Liveness = yl
elseif yl === BOT_LIVENESS
Liveness = xl
else
Liveness = xl ∪ yl
end
return EscapeInfo(
x.Analyzed | y.Analyzed,
x.ReturnEscape | y.ReturnEscape,
ThrownEscape,
AliasInfo,
Liveness,
)
end
function merge_alias_info(@nospecialize(xa), @nospecialize(ya))
if xa === true || ya === true
return true
elseif xa === false
return ya
elseif ya === false
return xa
elseif isa(xa, IndexableFields)
if isa(ya, IndexableFields)
xinfos, yinfos = xa.infos, ya.infos
xn, yn = length(xinfos), length(yinfos)
nmax, nmin = max(xn, yn), min(xn, yn)
infos = Vector{AInfo}(undef, nmax)
for i in 1:nmax
if i > nmin
infos[i] = (xn > yn ? xinfos : yinfos)[i]
else
infos[i] = xinfos[i] ∪ yinfos[i]
end
end
return IndexableFields(infos)
elseif isa(ya, Unindexable)
xinfos, yinfo = xa.infos, ya.info
return merge_to_unindexable(ya, xa)
else
return true # handle conflicting case conservatively
end
elseif isa(xa, IndexableElements)
if isa(ya, IndexableElements)
xinfos, yinfos = xa.infos, ya.infos
infos = IdDict{Int,AInfo}()
for idx in keys(xinfos)
if !haskey(yinfos, idx)
infos[idx] = xinfos[idx]
else
infos[idx] = xinfos[idx] ∪ yinfos[idx]
end
end
for idx in keys(yinfos)
haskey(xinfos, idx) && continue # unioned already
infos[idx] = yinfos[idx]
end
return IndexableElements(infos)
elseif isa(ya, Unindexable)
return merge_to_unindexable(ya, xa)
else
return true # handle conflicting case conservatively
end
else
xa = xa::Unindexable
if isa(ya, IndexableFields)
return merge_to_unindexable(xa, ya)
elseif isa(ya, IndexableElements)
return merge_to_unindexable(xa, ya)
else
ya = ya::Unindexable
xinfo, yinfo = xa.info, ya.info
info = xinfo ∪ yinfo
return Unindexable(info)
end
end
end
const AliasSet = IntDisjointSet{Int}
const ArrayInfo = IdDict{Int,Vector{Int}}
"""
estate::EscapeState
Extended lattice that maps arguments and SSA values to escape information represented as [`EscapeInfo`](@ref).
Escape information imposed on SSA IR element `x` can be retrieved by `estate[x]`.
"""
struct EscapeState
escapes::Vector{EscapeInfo}
aliasset::AliasSet
nargs::Int
arrayinfo::Union{Nothing,ArrayInfo}
end
function EscapeState(nargs::Int, nstmts::Int, arrayinfo::Union{Nothing,ArrayInfo})
escapes = EscapeInfo[
1 ≤ i ≤ nargs ? ArgEscape() : ⊥ for i in 1:(nargs+nstmts)]
aliasset = AliasSet(nargs+nstmts)
return EscapeState(escapes, aliasset, nargs, arrayinfo)
end
function getindex(estate::EscapeState, @nospecialize(x))
xidx = iridx(x, estate)
return xidx === nothing ? nothing : estate.escapes[xidx]
end
function setindex!(estate::EscapeState, v::EscapeInfo, @nospecialize(x))
xidx = iridx(x, estate)
if xidx !== nothing
estate.escapes[xidx] = v
end
return estate
end
"""
iridx(x, estate::EscapeState) -> xidx::Union{Int,Nothing}
Tries to convert analyzable IR element `x::Union{Argument,SSAValue}` to
its unique identifier number `xidx` that is valid in the analysis context of `estate`.
Returns `nothing` if `x` isn't maintained by `estate` and thus unanalyzable (e.g. `x::GlobalRef`).
`irval` is the inverse function of `iridx` (not formally), i.e.
`irval(iridx(x::Union{Argument,SSAValue}, state), state) === x`.
"""
function iridx(@nospecialize(x), estate::EscapeState)
if isa(x, Argument)
xidx = x.n
@assert 1 ≤ xidx ≤ estate.nargs "invalid Argument"
elseif isa(x, SSAValue)
xidx = x.id + estate.nargs
else
return nothing
end
return xidx
end
"""
irval(xidx::Int, estate::EscapeState) -> x::Union{Argument,SSAValue}
Converts its unique identifier number `xidx` to the original IR element `x::Union{Argument,SSAValue}`
that is analyzable in the context of `estate`.
`iridx` is the inverse function of `irval` (not formally), i.e.
`iridx(irval(xidx, state), state) === xidx`.
"""
function irval(xidx::Int, estate::EscapeState)
x = xidx > estate.nargs ? SSAValue(xidx-estate.nargs) : Argument(xidx)
return x
end
function getaliases(x::Union{Argument,SSAValue}, estate::EscapeState)
xidx = iridx(x, estate)
aliases = getaliases(xidx, estate)
aliases === nothing && return nothing
return Union{Argument,SSAValue}[irval(aidx, estate) for aidx in aliases]
end
function getaliases(xidx::Int, estate::EscapeState)
aliasset = estate.aliasset
root = find_root!(aliasset, xidx)
if xidx ≠ root || aliasset.ranks[xidx] > 0
# the size of this alias set containing `key` is larger than 1,
# collect the entire alias set
aliases = Int[]
for aidx in 1:length(aliasset.parents)
if aliasset.parents[aidx] == root
push!(aliases, aidx)
end
end
return aliases
else
return nothing
end
end
isaliased(x::Union{Argument,SSAValue}, y::Union{Argument,SSAValue}, estate::EscapeState) =
isaliased(iridx(x, estate), iridx(y, estate), estate)
isaliased(xidx::Int, yidx::Int, estate::EscapeState) =
in_same_set(estate.aliasset, xidx, yidx)
struct ArgEscapeInfo
EscapeBits::UInt8
end
function ArgEscapeInfo(x::EscapeInfo)
x === ⊤ && return ArgEscapeInfo(ARG_ALL_ESCAPE)
EscapeBits = 0x00
has_return_escape(x) && (EscapeBits |= ARG_RETURN_ESCAPE)
has_thrown_escape(x) && (EscapeBits |= ARG_THROWN_ESCAPE)
return ArgEscapeInfo(EscapeBits)
end
const ARG_ALL_ESCAPE = 0x01 << 0
const ARG_RETURN_ESCAPE = 0x01 << 1
const ARG_THROWN_ESCAPE = 0x01 << 2
has_no_escape(x::ArgEscapeInfo) = !has_all_escape(x) && !has_return_escape(x) && !has_thrown_escape(x)
has_all_escape(x::ArgEscapeInfo) = x.EscapeBits & ARG_ALL_ESCAPE ≠ 0
has_return_escape(x::ArgEscapeInfo) = x.EscapeBits & ARG_RETURN_ESCAPE ≠ 0
has_thrown_escape(x::ArgEscapeInfo) = x.EscapeBits & ARG_THROWN_ESCAPE ≠ 0
struct ArgAliasing
aidx::Int
bidx::Int
end
struct ArgEscapeCache
argescapes::Vector{ArgEscapeInfo}
argaliases::Vector{ArgAliasing}
end
function ArgEscapeCache(estate::EscapeState)
nargs = estate.nargs
argescapes = Vector{ArgEscapeInfo}(undef, nargs)
argaliases = ArgAliasing[]
for i = 1:nargs
info = estate.escapes[i]
@assert info.AliasInfo === true
argescapes[i] = ArgEscapeInfo(info)
for j = (i+1):nargs
if isaliased(i, j, estate)
push!(argaliases, ArgAliasing(i, j))
end
end
end
return ArgEscapeCache(argescapes, argaliases)
end
"""
is_ipo_profitable(ir::IRCode, nargs::Int) -> Bool
Heuristically checks if there is any profitability to run the escape analysis on `ir`
and generate IPO escape information cache. Specifically, this function examines
if any call argument is "interesting" in terms of their escapability.
"""
function is_ipo_profitable(ir::IRCode, nargs::Int)
for i = 1:nargs
t = unwrap_unionall(widenconst(ir.argtypes[i]))
t <: IO && return false # bail out IO-related functions
is_ipo_profitable_type(t) && return true
end
return false
end
function is_ipo_profitable_type(@nospecialize t)
if isa(t, Union)
return is_ipo_profitable_type(t.a) && is_ipo_profitable_type(t.b)
end
(t === String || t === Symbol || t === Module || t === SimpleVector) && return false
return ismutabletype(t)
end
abstract type Change end
struct EscapeChange <: Change
xidx::Int
xinfo::EscapeInfo
end
struct AliasChange <: Change
xidx::Int
yidx::Int
end
struct ArgAliasChange <: Change
xidx::Int
yidx::Int
end
struct LivenessChange <: Change
xidx::Int
livepc::Int
end
const Changes = Vector{Change}
struct AnalysisState{T<:Callable}
ir::IRCode
estate::EscapeState
changes::Changes
get_escape_cache::T
end
function getinst(ir::IRCode, idx::Int)
nstmts = length(ir.stmts)
if idx ≤ nstmts
return ir.stmts[idx]
else
return ir.new_nodes.stmts[idx - nstmts]
end
end
"""
analyze_escapes(ir::IRCode, nargs::Int, call_resolved::Bool, get_escape_cache::Callable)
-> estate::EscapeState
Analyzes escape information in `ir`:
- `nargs`: the number of actual arguments of the analyzed call
- `call_resolved`: if interprocedural calls are already resolved by `ssa_inlining_pass!`
- `get_escape_cache(::Union{InferenceResult,MethodInstance}) -> Union{Nothing,ArgEscapeCache}`:
retrieves cached argument escape information
"""
function analyze_escapes(ir::IRCode, nargs::Int, call_resolved::Bool, get_escape_cache::T) where T<:Callable
stmts = ir.stmts
nstmts = length(stmts) + length(ir.new_nodes.stmts)
tryregions, arrayinfo, callinfo = compute_frameinfo(ir, call_resolved)
estate = EscapeState(nargs, nstmts, arrayinfo)
changes = Changes() # keeps changes that happen at current statement
astate = AnalysisState(ir, estate, changes, get_escape_cache)
local debug_itr_counter = 0
while true
local anyupdate = false
for pc in nstmts:-1:1
stmt = getinst(ir, pc)[:inst]
# collect escape information
if isa(stmt, Expr)
head = stmt.head
if head === :call
if callinfo !== nothing
escape_call!(astate, pc, stmt.args, callinfo)
else
escape_call!(astate, pc, stmt.args)
end
elseif head === :invoke
escape_invoke!(astate, pc, stmt.args)
elseif head === :new || head === :splatnew
escape_new!(astate, pc, stmt.args)
elseif head === :(=)
lhs, rhs = stmt.args
if isa(lhs, GlobalRef) # global store
add_escape_change!(astate, rhs, ⊤)
else
unexpected_assignment!(ir, pc)
end
elseif head === :foreigncall
escape_foreigncall!(astate, pc, stmt.args)
elseif head === :throw_undef_if_not # XXX when is this expression inserted ?
add_escape_change!(astate, stmt.args[1], ThrownEscape(pc))
elseif is_meta_expr_head(head)
# meta expressions doesn't account for any usages
continue
elseif head === :enter || head === :leave || head === :the_exception || head === :pop_exception
# ignore these expressions since escapes via exceptions are handled by `escape_exception!`
# `escape_exception!` conservatively propagates `AllEscape` anyway,
# and so escape information imposed on `:the_exception` isn't computed
continue
elseif head === :static_parameter || # this exists statically, not interested in its escape
head === :copyast || # XXX can this account for some escapes?
head === :undefcheck || # XXX can this account for some escapes?
head === :isdefined || # just returns `Bool`, nothing accounts for any escapes
head === :gc_preserve_begin || # `GC.@preserve` expressions themselves won't be used anywhere
head === :gc_preserve_end # `GC.@preserve` expressions themselves won't be used anywhere
continue
else
add_conservative_changes!(astate, pc, stmt.args)
end
elseif isa(stmt, ReturnNode)
if isdefined(stmt, :val)
add_escape_change!(astate, stmt.val, ReturnEscape(pc))
end
elseif isa(stmt, PhiNode)
escape_edges!(astate, pc, stmt.values)
elseif isa(stmt, PiNode)
escape_val_ifdefined!(astate, pc, stmt)
elseif isa(stmt, PhiCNode)
escape_edges!(astate, pc, stmt.values)
elseif isa(stmt, UpsilonNode)
escape_val_ifdefined!(astate, pc, stmt)
elseif isa(stmt, GlobalRef) # global load
add_escape_change!(astate, SSAValue(pc), ⊤)
elseif isa(stmt, SSAValue)
escape_val!(astate, pc, stmt)
elseif isa(stmt, Argument)
escape_val!(astate, pc, stmt)
else # otherwise `stmt` can be GotoNode, GotoIfNot, and inlined values etc.
continue
end
isempty(changes) && continue
anyupdate |= propagate_changes!(estate, changes)
empty!(changes)
end
tryregions !== nothing && escape_exception!(astate, tryregions)
debug_itr_counter += 1
anyupdate || break
end
# if debug_itr_counter > 2
# println("[EA] excessive iteration count found ", debug_itr_counter, " (", singleton_type(ir.argtypes[1]), ")")
# end
return estate
end
"""
compute_frameinfo(ir::IRCode, call_resolved::Bool) -> (tryregions, arrayinfo, callinfo)
A preparatory linear scan before the escape analysis on `ir` to find:
- `tryregions::Union{Nothing,Vector{UnitRange{Int}}}`: regions in which potential `throw`s can be caught (used by `escape_exception!`)
- `arrayinfo::Union{Nothing,IdDict{Int,Vector{Int}}}`: array allocations whose dimensions are known precisely (with some very simple local analysis)
- `callinfo::`: when `!call_resolved`, `compute_frameinfo` additionally returns `callinfo::Vector{Union{MethodInstance,InferenceResult}}`,
which contains information about statically resolved callsites.
The inliner will use essentially equivalent interprocedural information to inline callees as well as resolve static callsites,
this additional information won't be required when analyzing post-inlining IR.
!!! note
This array dimension analysis to compute `arrayinfo` is very local and doesn't account
for flow-sensitivity nor complex aliasing.
Ideally this dimension analysis should be done as a part of type inference that
propagates array dimenstions in a flow sensitive way.
"""
function compute_frameinfo(ir::IRCode, call_resolved::Bool)
nstmts, nnewnodes = length(ir.stmts), length(ir.new_nodes.stmts)
tryregions, arrayinfo = nothing, nothing
if !call_resolved
callinfo = Vector{Any}(undef, nstmts+nnewnodes)
else
callinfo = nothing
end
for idx in 1:nstmts+nnewnodes
inst = getinst(ir, idx)
stmt = inst[:inst]
if !call_resolved
# TODO don't call `check_effect_free!` in the inlinear
check_effect_free!(ir, idx, stmt, inst[:type])
end
if callinfo !== nothing && isexpr(stmt, :call)
callinfo[idx] = resolve_call(ir, stmt, inst[:info])
elseif isexpr(stmt, :enter)
@assert idx ≤ nstmts "try/catch inside new_nodes unsupported"
tryregions === nothing && (tryregions = UnitRange{Int}[])
leave_block = stmt.args[1]::Int
leave_pc = first(ir.cfg.blocks[leave_block].stmts)
push!(tryregions, idx:leave_pc)
elseif isexpr(stmt, :foreigncall)
args = stmt.args
name = args[1]
nn = normalize(name)
isa(nn, Symbol) || @goto next_stmt
ndims = alloc_array_ndims(nn)
ndims === nothing && @goto next_stmt
if ndims ≠ 0
length(args) ≥ ndims+6 || @goto next_stmt
dims = Int[]
for i in 1:ndims
dim = argextype(args[i+6], ir)
isa(dim, Const) || @goto next_stmt
dim = dim.val
isa(dim, Int) || @goto next_stmt
push!(dims, dim)
end
else
length(args) ≥ 7 || @goto next_stmt
dims = argextype(args[7], ir)
if isa(dims, Const)
dims = dims.val
isa(dims, Tuple{Vararg{Int}}) || @goto next_stmt
dims = collect(Int, dims)
else
dims === Tuple{} || @goto next_stmt
dims = Int[]
end
end
if arrayinfo === nothing
arrayinfo = ArrayInfo()
end
arrayinfo[idx] = dims
elseif arrayinfo !== nothing
# TODO this super limited alias analysis is able to handle only very simple cases
# this should be replaced with a proper forward dimension analysis
if isa(stmt, PhiNode)
values = stmt.values
local dims = nothing
for i = 1:length(values)
if isassigned(values, i)
val = values[i]
if isa(val, SSAValue) && haskey(arrayinfo, val.id)
if dims === nothing
dims = arrayinfo[val.id]
continue
elseif dims == arrayinfo[val.id]
continue
end
end
end
@goto next_stmt
end
if dims !== nothing
arrayinfo[idx] = dims
end
elseif isa(stmt, PiNode)
if isdefined(stmt, :val)
val = stmt.val
if isa(val, SSAValue) && haskey(arrayinfo, val.id)
arrayinfo[idx] = arrayinfo[val.id]
end
end
end
end
@label next_stmt
end
return tryregions, arrayinfo, callinfo
end
# define resolve_call
if _TOP_MOD === Core.Compiler
include("compiler/ssair/EscapeAnalysis/interprocedural.jl")
else
include("interprocedural.jl")
end
# propagate changes, and check convergence
function propagate_changes!(estate::EscapeState, changes::Changes)
local anychanged = false
for change in changes
if isa(change, EscapeChange)
anychanged |= propagate_escape_change!(estate, change)
elseif isa(change, LivenessChange)
anychanged |= propagate_liveness_change!(estate, change)
else
change = change::AliasChange
anychanged |= propagate_alias_change!(estate, change)
end
end
return anychanged
end
@inline propagate_escape_change!(estate::EscapeState, change::EscapeChange) =
propagate_escape_change!(⊔ₑ, estate, change)
# allows this to work as lattice join as well as lattice meet
@inline function propagate_escape_change!(@specialize(op),
estate::EscapeState, change::EscapeChange)
(; xidx, xinfo) = change
anychanged = _propagate_escape_change!(op, estate, xidx, xinfo)
# COMBAK is there a more efficient method of escape information equalization on aliasset?
aliases = getaliases(xidx, estate)
if aliases !== nothing
for aidx in aliases
anychanged |= _propagate_escape_change!(op, estate, aidx, xinfo)
end
end
return anychanged
end
@inline function _propagate_escape_change!(@specialize(op),
estate::EscapeState, xidx::Int, info::EscapeInfo)
old = estate.escapes[xidx]
new = op(old, info)
if old ≠ new
estate.escapes[xidx] = new
return true
end
return false
end
# propagate Liveness changes separately in order to avoid constructing too many LivenessSet
@inline function propagate_liveness_change!(estate::EscapeState, change::LivenessChange)
(; xidx, livepc) = change
info = estate.escapes[xidx]
Liveness = info.Liveness
Liveness === TOP_LIVENESS && return false
livepc in Liveness && return false
if Liveness === BOT_LIVENESS || Liveness === ARG_LIVENESS
# if this Liveness is a constant, we shouldn't modify it and propagate this change as a new EscapeInfo
Liveness = copy(Liveness)
push!(Liveness, livepc)
estate.escapes[xidx] = EscapeInfo(info; Liveness)
return true
else
# directly modify Liveness property in order to avoid excessive copies
push!(Liveness, livepc)
return true
end
end
@inline function propagate_alias_change!(estate::EscapeState, change::AliasChange)
anychange = false
(; xidx, yidx) = change
aliasset = estate.aliasset
xroot = find_root!(aliasset, xidx)
yroot = find_root!(aliasset, yidx)
if xroot ≠ yroot
union!(aliasset, xroot, yroot)
return true
end
return false
end
function add_escape_change!(astate::AnalysisState, @nospecialize(x), xinfo::EscapeInfo,
force::Bool = false)
xinfo === ⊥ && return nothing # performance optimization
xidx = iridx(x, astate.estate)
if xidx !== nothing
if force || !isbitstype(widenconst(argextype(x, astate.ir)))
push!(astate.changes, EscapeChange(xidx, xinfo))
end
end
return nothing
end
function add_liveness_change!(astate::AnalysisState, @nospecialize(x), livepc::Int)
xidx = iridx(x, astate.estate)
if xidx !== nothing
if !isbitstype(widenconst(argextype(x, astate.ir)))
push!(astate.changes, LivenessChange(xidx, livepc))
end
end
return nothing
end
function add_alias_change!(astate::AnalysisState, @nospecialize(x), @nospecialize(y))
if isa(x, GlobalRef)
return add_escape_change!(astate, y, ⊤)
elseif isa(y, GlobalRef)
return add_escape_change!(astate, x, ⊤)
end
estate = astate.estate
xidx = iridx(x, estate)
yidx = iridx(y, estate)
if xidx !== nothing && yidx !== nothing
if !isaliased(xidx, yidx, astate.estate)
pushfirst!(astate.changes, AliasChange(xidx, yidx))
end
# add new escape change here so that it's shared among the expanded `aliasset` in `propagate_escape_change!`
xinfo = estate.escapes[xidx]
yinfo = estate.escapes[yidx]
add_escape_change!(astate, x, xinfo ⊔ₑ yinfo, #=force=#true)
end
return nothing
end
struct LocalDef
idx::Int
end