: interval-[30,46] ( -- live-interval )
T{ live-interval-state
{ vreg 49 }
- { start 30 } { end 46 }
{ ranges { { 30 46 } } }
{ uses
{
: interval-[30,60] ( -- live-interval )
T{ live-interval-state
{ vreg 25 }
- { start 30 } { end 60 }
+ { ranges { { 30 60 } } }
{ reg RAX }
} ;
{ int-regs V{
T{ live-interval-state
{ vreg 1 }
- { start 30 }
- { end 40 }
{ ranges { { 30 40 } } }
{ uses
{ T{ vreg-use { n 32 } { def-rep double-rep } } }
}
T{ live-interval-state
{ vreg 50 }
- { start 5 }
- { end 10 }
{ ranges { { 5 10 } } }
{ uses
{ T{ vreg-use { n 8 } { def-rep double-rep } } }
GENERIC: handle ( obj -- )
M: live-interval-state handle
- [ start>> [ deactivate-intervals ] [ activate-intervals ] bi ]
+ [
+ live-interval-start
+ [ deactivate-intervals ] [ activate-intervals ] bi
+ ]
[ registers get assign-register ] bi ;
: handle-sync-point ( sync-point active-intervals -- )
{ vreg 45 }
{ spill-to T{ spill-slot { n 8 } } }
{ spill-rep double-rep }
- { start 22 }
- { end 47 }
{ ranges { { 22 47 } { 67 68 } { 69 72 } } }
{ uses
{
[ ]
[ assign-spill ]
[ trim-before-ranges ]
- [ compute-start/end ]
[ check-ranges ]
} cleave
] if ;
[ ]
[ assign-reload ]
[ trim-after-ranges ]
- [ compute-start/end ]
[ check-ranges ]
} cleave
] if ;
split-interval [ spill-before ] [ spill-after ] bi* ;
: find-next-use ( live-interval new -- n )
- [ uses>> ] [ start>> ] bi*
+ [ uses>> ] [ live-interval-start ] bi*
'[ [ spill-slot?>> not ] [ n>> ] bi _ >= and ] find nip
[ n>> ] [ 1/0. ] if* ;
:: spill-intersecting-active ( new reg -- )
new active-intervals-for [ [ reg>> reg = ] find swap dup ] keep
- '[ _ remove-nth! drop new start>> spill ] [ 2drop ] if ;
+ '[ _ remove-nth! drop new live-interval-start spill ] [ 2drop ] if ;
:: spill-intersecting-inactive ( new reg -- )
new inactive-intervals-for [
dup reg>> reg = [
dup new intervals-intersect? [
- new start>> spill f
+ new live-interval-start spill f
] [ drop t ] if
] [ drop t ] if
] filter! drop ;
: check-split ( live-interval n -- )
check-allocation? get [
- [ [ start>> ] dip > [ splitting-too-early ] when ]
- [ [ end>> ] dip < [ splitting-too-late ] when ]
+ [ [ live-interval-start ] dip > [ splitting-too-early ] when ]
+ [ [ live-interval-end ] dip < [ splitting-too-late ] when ]
[
- drop [ end>> ] [ start>> ] bi =
+ drop ranges>> ranges-endpoints =
[ splitting-atomic-interval ] when
] 2tri
] [ 2drop ] if ; inline
{ } [
40 progress set
T{ live-interval-state
- { end 34 }
{ vreg 123 }
+ { ranges { { 0 0 } { 30 34 } } }
}
check-handled
] unit-test
T{ sync-point { n 33 } } interval/sync-point-key
] unit-test
+{ { 0 34 123 } } [
+ T{ live-interval-state
+ { vreg 123 }
+ { ranges { { 0 0 } { 30 34 } } }
+ } interval/sync-point-key
+] unit-test
+
! next-spill-slot
{
T{ spill-slot f 0 }
{ { 5 1/0. 1/0. } T{ sync-point { n 5 } } }
{
{ 20 28 f }
- T{ live-interval-state { start 20 } { end 28 } }
+ T{ live-interval-state { ranges { { 20 28 } } } }
}
{
{ 20 30 f }
- T{ live-interval-state { start 20 } { end 30 } }
+ T{ live-interval-state { ranges { { 20 30 } } } }
}
{
{ 33 999 f }
- T{ live-interval-state { start 33 } { end 999 } }
+ T{ live-interval-state { ranges { { 33 999 } } } }
}
{ { 33 1/0. 1/0. } T{ sync-point { n 33 } } }
{ { 100 1/0. 1/0. } T{ sync-point { n 100 } } }
}
} [
{
- T{ live-interval-state { start 20 } { end 30 } }
- T{ live-interval-state { start 20 } { end 28 } }
- T{ live-interval-state { start 33 } { end 999 } }
+ T{ live-interval-state { ranges { { 20 30 } } } }
+ T{ live-interval-state { ranges { { 20 28 } } } }
+ T{ live-interval-state { ranges { { 33 999 } } } }
T{ sync-point { n 5 } }
T{ sync-point { n 33 } }
T{ sync-point { n 100 } }
{ 2 } [
{
- T{ live-interval-state { start 20 } { end 30 } }
- T{ live-interval-state { start 20 } { end 30 } }
+ T{ live-interval-state { ranges { { 20 30 } } } }
+ T{ live-interval-state { ranges { { 20 30 } } } }
} >unhandled-min-heap heap-size
] unit-test
SYMBOL: progress
: check-unhandled ( live-interval -- )
- start>> progress get <= [ "check-unhandled" throw ] when ; inline
+ live-interval-start progress get <= [ "check-unhandled" throw ] when ; inline
: check-handled ( live-interval -- )
- end>> progress get > [ "check-handled" throw ] when ; inline
+ live-interval-end progress get > [ "check-handled" throw ] when ; inline
SYMBOL: unhandled-min-heap
GENERIC: interval/sync-point-key ( interval/sync-point -- key )
M: live-interval-state interval/sync-point-key
- [ start>> ] [ end>> ] [ vreg>> ] tri 3array ;
+ [ ranges>> ranges-endpoints ] [ vreg>> ] bi 3array ;
M: sync-point interval/sync-point-key
n>> 1/0. 1/0. 3array ;
: add-handled ( live-interval -- )
[ check-handled ] [ handled-intervals get push ] bi ;
-: finished? ( n live-interval -- ? ) end>> swap < ;
+: finished? ( n live-interval -- ? ) live-interval-end swap < ;
: finish ( n live-interval -- keep? )
nip add-handled f ;
[ [ min ] when* ] change-at ;
: register-available? ( new result -- ? )
- [ end>> ] [ second ] bi* < ; inline
+ [ live-interval-end ] [ second ] bi* < ; inline
: register-available ( new result -- )
first >>reg add-active ;
SYMBOL: pending-interval-assoc
: add-pending ( live-interval -- )
- [ dup end>> pending-interval-heap get heap-push ]
+ [ dup live-interval-end pending-interval-heap get heap-push ]
[ [ reg>> ] [ vreg>> ] bi pending-interval-assoc get set-at ]
bi ;
] change-instructions compute-live-out ;
: init-assignment ( live-intervals -- )
- [ [ start>> ] map ] keep zip >min-heap unhandled-intervals namespaces:set
+ [ [ live-interval-start ] map ] keep zip
+ >min-heap unhandled-intervals namespaces:set
<min-heap> pending-interval-heap namespaces:set
H{ } clone pending-interval-assoc namespaces:set
H{ } clone machine-live-ins namespaces:set
] unit-test
{ 0 0 } [
- 1 live-intervals get at [ start>> ] [ end>> ] bi
+ 1 live-intervals get at ranges>> ranges-endpoints
] unit-test
! Live interval splitting
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 2 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
{ ranges V{ { 0 2 } } }
{ spill-to T{ spill-slot f 0 } }
}
T{ live-interval-state
{ vreg 1 }
- { start 5 }
- { end 5 }
{ uses V{ T{ vreg-use f 5 f float-rep } } }
{ ranges V{ { 5 5 } } }
{ reload-from T{ spill-slot f 0 } }
} [
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 5 }
{ uses
V{
T{ vreg-use f 0 float-rep f }
f
T{ live-interval-state
{ vreg 2 }
- { start 1 }
- { end 5 }
{ uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
{ ranges V{ { 1 5 } } }
{ reload-from T{ spill-slot f 4 } }
} [
T{ live-interval-state
{ vreg 2 }
- { start 0 }
- { end 5 }
{ uses
V{
T{ vreg-use f 0 float-rep f }
{
T{ live-interval-state
{ vreg 3 }
- { start 0 }
- { end 2 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
{ ranges V{ { 0 2 } } }
{ spill-to T{ spill-slot f 8 } }
} [
T{ live-interval-state
{ vreg 3 }
- { start 0 }
- { end 5 }
{ uses
V{
T{ vreg-use f 0 float-rep f }
{
T{ live-interval-state
{ vreg 4 }
- { start 0 }
- { end 1 }
{ uses V{ T{ vreg-use f 0 float-rep f } } }
{ ranges V{ { 0 1 } } }
{ spill-to T{ spill-slot f 12 } }
}
T{ live-interval-state
{ vreg 4 }
- { start 20 }
- { end 30 }
{ uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
{ ranges V{ { 20 30 } } }
{ reload-from T{ spill-slot f 12 } }
} [
T{ live-interval-state
{ vreg 4 }
- { start 0 }
- { end 30 }
{ uses
V{
T{ vreg-use f 0 float-rep f }
{
T{ live-interval-state
{ vreg 5 }
- { start 0 }
- { end 1 }
{ uses V{ T{ vreg-use f 0 float-rep f } } }
{ ranges V{ { 0 1 } } }
{ spill-to T{ spill-slot f 16 } }
}
T{ live-interval-state
{ vreg 5 }
- { start 20 }
- { end 30 }
{ uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
{ ranges V{ { 20 30 } } }
}
} [
T{ live-interval-state
{ vreg 5 }
- { start 0 }
- { end 30 }
{ uses
V{
T{ vreg-use f 0 float-rep f }
{
T{ live-interval-state
{ vreg 6 }
- { start 0 }
- { end 11 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
{ ranges V{ { 0 11 } } }
{ spill-to T{ spill-slot f 24 } }
}
T{ live-interval-state
{ vreg 6 }
- { start 20 }
- { end 20 }
{ uses V{ T{ vreg-use f 20 f double-rep } } }
{ ranges V{ { 20 20 } } }
{ reload-from T{ spill-slot f 24 } }
} [
T{ live-interval-state
{ vreg 6 }
- { start 0 }
- { end 20 }
{ uses
V{
T{ vreg-use f 0 float-rep f }
f
T{ live-interval-state
{ vreg 7 }
- { start 8 }
- { end 8 }
{ ranges V{ { 8 8 } } }
{ uses V{ T{ vreg-use f 8 int-rep } } }
}
} [
T{ live-interval-state
{ vreg 7 }
- { start 4 }
- { end 8 }
{ ranges V{ { 4 8 } } }
{ uses V{ T{ vreg-use f 8 int-rep } } }
} 4 split-for-spill
{
T{ live-interval-state
{ vreg 8 }
- { start 0 }
- { end 3 }
{ ranges V{ { 0 3 } } }
{ uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
{ spill-to T{ spill-slot f 32 } }
}
T{ live-interval-state
{ vreg 8 }
- { start 14 }
- { end 16 }
{ ranges V{ { 14 16 } } }
{ uses V{ T{ vreg-use f 14 f int-rep } } }
{ reload-from T{ spill-slot f 32 } }
} [
T{ live-interval-state
{ vreg 8 }
- { start 0 }
- { end 16 }
{ ranges V{ { 0 4 } { 6 10 } { 12 16 } } }
{ uses
V{
T{ live-interval-state
{ vreg 1 }
{ reg 1 }
- { start 1 }
- { end 15 }
+ { ranges { { 1 15 } } }
{ uses
V{
T{ vreg-use f 1 int-rep f }
T{ live-interval-state
{ vreg 2 }
{ reg 2 }
- { start 3 }
- { end 8 }
+ { ranges { { 3 8 } } }
{ uses
V{
T{ vreg-use f 3 int-rep f }
T{ live-interval-state
{ vreg 3 }
{ reg 3 }
- { start 3 }
- { end 10 }
+ { ranges { { 3 10 } } }
{ uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
}
}
} active-intervals set
H{ } inactive-intervals set
T{ live-interval-state
- { vreg 1 }
- { start 5 }
- { end 5 }
- { uses V{ T{ vreg-use f 5 int-rep f } } }
+ { vreg 1 }
+ { ranges { { 5 5 } } }
+ { uses V{ T{ vreg-use f 5 int-rep f } } }
}
spill-status
] unit-test
T{ live-interval-state
{ vreg 1 }
{ reg 1 }
- { start 1 }
- { end 15 }
+ { ranges { { 1 15 } } }
{ uses V{ T{ vreg-use f 1 int-rep f } } }
}
T{ live-interval-state
{ vreg 2 }
{ reg 2 }
- { start 3 }
- { end 8 }
{ uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
}
}
} active-intervals set
H{ } inactive-intervals set
T{ live-interval-state
- { vreg 3 }
- { start 5 }
- { end 5 }
- { uses V{ T{ vreg-use f 5 int-rep f } } }
+ { vreg 3 }
+ { ranges { { 5 5 } } }
+ { uses V{ T{ vreg-use f 5 int-rep f } } }
}
spill-status
] unit-test
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
{ ranges V{ { 0 100 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 10 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
{ ranges V{ { 0 10 } } }
}
T{ live-interval-state
{ vreg 2 }
- { start 11 }
- { end 20 }
{ uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
{ ranges V{ { 11 20 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
{ ranges V{ { 0 100 } } }
}
T{ live-interval-state
{ vreg 2 }
- { start 30 }
- { end 60 }
{ uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
{ ranges V{ { 30 60 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
{ ranges V{ { 0 100 } } }
}
T{ live-interval-state
{ vreg 2 }
- { start 30 }
- { end 200 }
{ uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
{ ranges V{ { 30 200 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
{ ranges V{ { 0 100 } } }
}
T{ live-interval-state
{ vreg 2 }
- { start 30 }
- { end 100 }
{ uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
{ ranges V{ { 30 100 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 20 }
{ uses
V{
T{ vreg-use f 0 int-rep f }
}
T{ live-interval-state
{ vreg 2 }
- { start 0 }
- { end 20 }
{ uses
V{
T{ vreg-use f 0 int-rep f }
}
T{ live-interval-state
{ vreg 3 }
- { start 4 }
- { end 8 }
{ uses V{ T{ vreg-use f 6 int-rep f } } }
{ ranges V{ { 4 8 } } }
}
T{ live-interval-state
{ vreg 4 }
- { start 4 }
- { end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
{ ranges V{ { 4 8 } } }
}
! This guy will invoke the 'spill partially available' code path
T{ live-interval-state
{ vreg 5 }
- { start 4 }
- { end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
{ ranges V{ { 4 8 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 10 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 6 f int-rep } T{ vreg-use f 10 f int-rep } } }
{ ranges V{ { 0 10 } } }
}
! This guy will invoke the 'spill new' code path
T{ live-interval-state
{ vreg 5 }
- { start 2 }
- { end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
{ ranges V{ { 2 8 } } }
}
{
T{ live-interval-state
{ vreg 1 }
- { start 0 }
- { end 20 }
{ reg 0 }
{ ranges V{ { 0 2 } { 10 20 } } }
{ uses V{ 0 2 10 20 } }
T{ live-interval-state
{ vreg 2 }
- { start 4 }
- { end 40 }
{ reg 0 }
{ ranges V{ { 4 6 } { 30 40 } } }
{ uses V{ 4 6 30 40 } }
{
T{ live-interval-state
{ vreg 3 }
- { start 0 }
- { end 40 }
{ reg 1 }
{ ranges V{ { 0 40 } } }
{ uses V{ 0 40 } }
T{ live-interval-state
{ vreg 4 }
- { start 8 }
- { end 10 }
{ ranges V{ { 8 10 } } }
{ uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
}
IN: compiler.cfg.linear-scan.live-intervals.tests
: <live-interval-for-ranges> ( ranges -- live-interval )
- 10 <live-interval> [ '[ first2 _ ranges>> add-range ] each ] keep
- dup compute-start/end ;
+ 10 <live-interval> [ '[ first2 _ ranges>> add-range ] each ] keep ;
! cfg>sync-points
{
<basic-block> [ H{ { 4 4 } { 8 8 } { 9 9 } } 2array 1array live-outs set ]
[ handle-live-out ] bi live-intervals get
] unit-test
+
+! record-def
+{ } [
+ H{ { 37 37 } } leader-map set H{ { 37 int-rep } } representations set
+] unit-test
TUPLE: live-interval-state
vreg
reg spill-to spill-rep reload-from reload-rep
- start end ranges uses ;
+ ranges uses ;
: first-use ( live-interval -- use ) uses>> first ; inline
[ instructions>> <reversed> [ compute-live-intervals* ] each ]
} cleave ;
-: compute-start/end ( live-interval -- )
- dup ranges>> ranges-endpoints [ >>start ] [ >>end ] bi* drop ;
+: live-interval-start ( live-interval -- n )
+ ranges>> first first ; inline
+
+: live-interval-end ( live-interval -- n )
+ ranges>> last last ; inline
ERROR: bad-live-interval live-interval ;
: check-start ( live-interval -- )
- dup start>> -1 = [ bad-live-interval ] [ drop ] if ;
+ dup live-interval-start -1 = [ bad-live-interval ] [ drop ] if ;
: finish-live-intervals ( live-intervals -- )
[
{
[ [ { } like reverse! ] change-ranges drop ]
[ [ { } like reverse! ] change-uses drop ]
- [ compute-start/end ]
[ check-start ]
} cleave
] each ;