] when ;
! PowerPC backend sets frame-required? for ##integer>float!
-\ _spill t frame-required? set-word-prop
+\ ##spill t frame-required? set-word-prop
\ ##unary-float-function t frame-required? set-word-prop
\ ##binary-float-function t frame-required? set-word-prop
INSN: ##call-gc
literal: gc-roots ;
+! Spills and reloads, inserted by register allocator
+TUPLE: spill-slot { n integer } ;
+C: <spill-slot> spill-slot
+
+INSN: ##spill
+use: src
+literal: rep dst ;
+
+INSN: ##reload
+def: dst
+literal: rep src ;
+
! Instructions used by machine IR only.
+INSN: _spill-area-size
+literal: n ;
+
INSN: _prologue
literal: stack-frame ;
INSN: _conditional-branch
literal: label insn ;
-TUPLE: spill-slot { n integer } ;
-C: <spill-slot> spill-slot
-
-INSN: _spill
-use: src
-literal: rep dst ;
-
-INSN: _reload
-def: dst
-literal: rep src ;
-
-INSN: _spill-area-size
-literal: n ;
-
UNION: ##allocation
##allot
##box-alien
IN: compiler.cfg.linear-scan.allocation
: active-positions ( new assoc -- )
- [ vreg>> active-intervals-for ] dip
+ [ active-intervals-for ] dip
'[ [ 0 ] dip reg>> _ add-use-position ] each ;
: inactive-positions ( new assoc -- )
- [ [ vreg>> inactive-intervals-for ] keep ] dip
+ [ [ inactive-intervals-for ] keep ] dip
'[
[ _ relevant-ranges intersect-live-ranges 1/0. or ] [ reg>> ] bi
_ add-use-position
] [ drop ] if ;
: trim-before-ranges ( live-interval -- )
- [ ranges>> ] [ uses>> last n>> 1 + ] bi
+ [ ranges>> ] [ last-use n>> 1 + ] bi
[ '[ from>> _ <= ] filter! drop ]
[ swap last (>>to) ]
2bi ;
: trim-after-ranges ( live-interval -- )
- [ ranges>> ] [ uses>> first n>> ] bi
+ [ ranges>> ] [ first-use n>> ] bi
[ '[ to>> _ >= ] filter! drop ]
[ swap first (>>from) ]
2bi ;
'[ [ _ find-use-position ] [ reg>> ] bi _ add-use-position ] each ;
: active-positions ( new assoc -- )
- [ [ vreg>> active-intervals-for ] keep ] dip
+ [ [ active-intervals-for ] keep ] dip
find-use-positions ;
: inactive-positions ( new assoc -- )
[
- [ vreg>> inactive-intervals-for ] keep
+ [ inactive-intervals-for ] keep
[ '[ _ intervals-intersect? ] filter ] keep
] dip
find-use-positions ;
>alist alist-max ;
: spill-new? ( new pair -- ? )
- [ uses>> first n>> ] [ second ] bi* > ;
+ [ first-use n>> ] [ second ] bi* > ;
: spill-new ( new pair -- )
drop spill-after add-unhandled ;
! If there is an active interval using 'reg' (there should be at
! most one) are split and spilled and removed from the inactive
! set.
- new vreg>> active-intervals-for [ [ reg>> reg = ] find swap dup ] keep
+ new active-intervals-for [ [ reg>> reg = ] find swap dup ] keep
'[ _ remove-nth! drop new start>> spill ] [ 2drop ] if ;
:: spill-intersecting-inactive ( new reg -- )
! Any inactive intervals using 'reg' are split and spilled
! and removed from the inactive set.
- new vreg>> inactive-intervals-for [
+ new inactive-intervals-for [
dup reg>> reg = [
dup new intervals-intersect? [
new start>> spill f
! Vector of active live intervals
SYMBOL: active-intervals
-: active-intervals-for ( vreg -- seq )
- rep-of reg-class-of active-intervals get at ;
+: active-intervals-for ( live-interval -- seq )
+ reg-class>> active-intervals get at ;
: add-active ( live-interval -- )
- dup vreg>> active-intervals-for push ;
+ dup active-intervals-for push ;
: delete-active ( live-interval -- )
- dup vreg>> active-intervals-for remove-eq! drop ;
+ dup active-intervals-for remove-eq! drop ;
: assign-free-register ( new registers -- )
pop >>reg add-active ;
! Vector of inactive live intervals
SYMBOL: inactive-intervals
-: inactive-intervals-for ( vreg -- seq )
- rep-of reg-class-of inactive-intervals get at ;
+: inactive-intervals-for ( live-interval -- seq )
+ reg-class>> inactive-intervals get at ;
: add-inactive ( live-interval -- )
- dup vreg>> inactive-intervals-for push ;
+ dup inactive-intervals-for push ;
: delete-inactive ( live-interval -- )
- dup vreg>> inactive-intervals-for remove-eq! drop ;
+ dup inactive-intervals-for remove-eq! drop ;
! Vector of handled live intervals
SYMBOL: handled-intervals
: check-activate ( live-interval -- )
check-allocation? get [
- dup [ reg>> ] [ vreg>> active-intervals-for [ reg>> ] map ] bi member?
+ dup [ reg>> ] [ active-intervals-for [ reg>> ] map ] bi member?
[ register-already-used ] [ drop ] if
] [ drop ] if ;
! A utility used by register-status and spill-status words
: free-positions ( new -- assoc )
- vreg>> rep-of reg-class-of registers get at
+ reg-class>> registers get at
[ 1/0. ] H{ } <linked-assoc> map>assoc ;
: add-use-position ( n reg assoc -- ) [ [ min ] when* ] change-at ;
H{ } clone register-live-outs set
init-unhandled ;
+: spill-rep ( live-interval -- rep ) vreg>> rep-of ;
+
: insert-spill ( live-interval -- )
- [ reg>> ] [ vreg>> rep-of ] [ spill-to>> ] tri _spill ;
+ [ reg>> ] [ spill-rep ] [ spill-to>> ] tri ##spill ;
: handle-spill ( live-interval -- )
dup spill-to>> [ insert-spill ] [ drop ] if ;
: expire-old-intervals ( n -- )
pending-interval-heap get (expire-old-intervals) ;
+: reload-rep ( live-interval -- rep ) vreg>> rep-of ;
+
: insert-reload ( live-interval -- )
- [ reg>> ] [ vreg>> rep-of ] [ reload-from>> ] tri _reload ;
+ [ reg>> ] [ reload-rep ] [ reload-from>> ] tri ##reload ;
: insert-reload? ( live-interval -- ? )
! Don't insert a reload if the register will be written to
! before being read again.
{
[ reload-from>> ]
- [ uses>> first type>> +use+ eq? ]
+ [ first-use type>> +use+ eq? ]
} 1&& ;
: handle-reload ( live-interval -- )
[
T{ live-interval
{ vreg 1 }
+ { reg-class float-regs }
{ start 0 }
{ end 2 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } } }
}
T{ live-interval
{ vreg 1 }
+ { reg-class float-regs }
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 } } }
] [
T{ live-interval
{ vreg 1 }
+ { reg-class float-regs }
{ start 0 }
{ end 5 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } T{ vreg-use f 5 } } }
[
T{ live-interval
{ vreg 2 }
+ { reg-class float-regs }
{ start 0 }
{ end 1 }
{ uses V{ T{ vreg-use f 0 } } }
}
T{ live-interval
{ vreg 2 }
+ { reg-class float-regs }
{ start 1 }
{ end 5 }
{ uses V{ T{ vreg-use f 1 } T{ vreg-use f 5 } } }
] [
T{ live-interval
{ vreg 2 }
+ { reg-class float-regs }
{ start 0 }
{ end 5 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } T{ vreg-use f 5 } } }
[
T{ live-interval
{ vreg 3 }
+ { reg-class float-regs }
{ start 0 }
{ end 1 }
{ uses V{ T{ vreg-use f 0 } } }
}
T{ live-interval
{ vreg 3 }
+ { reg-class float-regs }
{ start 20 }
{ end 30 }
{ uses V{ T{ vreg-use f 20 } T{ vreg-use f 30 } } }
] [
T{ live-interval
{ vreg 3 }
+ { reg-class float-regs }
{ start 0 }
{ end 30 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 20 } T{ vreg-use f 30 } } }
V{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ reg 1 }
{ start 1 }
{ end 15 }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ reg 2 }
{ start 3 }
{ end 8 }
}
T{ live-interval
{ vreg 3 }
+ { reg-class int-regs }
{ reg 3 }
{ start 3 }
{ end 10 }
H{ } inactive-intervals set
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 } } }
V{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ reg 1 }
{ start 1 }
{ end 15 }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ reg 2 }
{ start 3 }
{ end 8 }
H{ } inactive-intervals set
T{ live-interval
{ vreg 3 }
+ { reg-class int-regs }
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 10 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } } }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ start 11 }
{ end 20 }
{ uses V{ T{ vreg-use f 11 } T{ vreg-use f 20 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ start 30 }
{ end 60 }
{ uses V{ T{ vreg-use f 30 } T{ vreg-use f 60 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ start 30 }
{ end 200 }
{ uses V{ T{ vreg-use f 30 } T{ vreg-use f 200 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ start 30 }
{ end 100 }
{ uses V{ T{ vreg-use f 30 } T{ vreg-use f 100 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 20 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } T{ vreg-use f 20 } } }
}
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ start 0 }
{ end 20 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } T{ vreg-use f 20 } } }
}
T{ live-interval
{ vreg 3 }
+ { reg-class int-regs }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 6 } } }
}
T{ live-interval
{ vreg 4 }
+ { reg-class int-regs }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 } } }
! This guy will invoke the 'spill partially available' code path
T{ live-interval
{ vreg 5 }
+ { reg-class int-regs }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 10 }
{ uses V{ T{ vreg-use f 0 } T{ vreg-use f 6 } T{ vreg-use f 10 } } }
! This guy will invoke the 'spill new' code path
T{ live-interval
{ vreg 5 }
+ { reg-class int-regs }
{ start 2 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 } } }
[ 5 ] [
T{ live-interval
{ start 0 }
+ { reg-class int-regs }
{ end 10 }
{ uses { 0 10 } }
{ ranges V{ T{ live-range f 0 10 } } }
}
T{ live-interval
{ start 5 }
+ { reg-class int-regs }
{ end 10 }
{ uses { 5 10 } }
{ ranges V{ T{ live-range f 5 10 } } }
{
T{ live-interval
{ vreg 1 }
+ { reg-class int-regs }
{ start 0 }
{ end 20 }
{ reg 0 }
T{ live-interval
{ vreg 2 }
+ { reg-class int-regs }
{ start 4 }
{ end 40 }
{ reg 0 }
{
T{ live-interval
{ vreg 3 }
+ { reg-class int-regs }
{ start 0 }
{ end 40 }
{ reg 1 }
} active-intervals set
T{ live-interval
- { vreg 4 }
+ { vreg 4 }
+ { reg-class int-regs }
{ start 8 }
{ end 10 }
{ ranges V{ T{ live-range f 8 10 } } }
[ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
-[ _spill ] [ 2 get successors>> first instructions>> first class ] unit-test
+[ ##spill ] [ 2 get successors>> first instructions>> first class ] unit-test
-[ _spill ] [ 3 get instructions>> second class ] unit-test
+[ ##spill ] [ 3 get instructions>> second class ] unit-test
-[ f ] [ 3 get instructions>> [ _reload? ] any? ] unit-test
+[ f ] [ 3 get instructions>> [ ##reload? ] any? ] unit-test
-[ _reload ] [ 4 get instructions>> first class ] unit-test
+[ ##reload ] [ 4 get instructions>> first class ] unit-test
! Resolve pass
V{
[ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
-[ t ] [ 2 get instructions>> [ _spill? ] any? ] unit-test
+[ t ] [ 2 get instructions>> [ ##spill? ] any? ] unit-test
-[ t ] [ 3 get predecessors>> first instructions>> [ _spill? ] any? ] unit-test
+[ t ] [ 3 get predecessors>> first instructions>> [ ##spill? ] any? ] unit-test
-[ t ] [ 5 get instructions>> [ _reload? ] any? ] unit-test
+[ t ] [ 5 get instructions>> [ ##reload? ] any? ] unit-test
! A more complicated failure case with resolve that came up after the above
! got fixed
[ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
-[ _spill ] [ 1 get instructions>> second class ] unit-test
-[ _reload ] [ 4 get instructions>> 4 swap nth class ] unit-test
-[ V{ 3 2 1 } ] [ 8 get instructions>> [ _spill? ] filter [ dst>> n>> cell / ] map ] unit-test
-[ V{ 3 2 1 } ] [ 9 get instructions>> [ _reload? ] filter [ src>> n>> cell / ] map ] unit-test
+[ ##spill ] [ 1 get instructions>> second class ] unit-test
+[ ##reload ] [ 4 get instructions>> 4 swap nth class ] unit-test
+[ V{ 3 2 1 } ] [ 8 get instructions>> [ ##spill? ] filter [ dst>> n>> cell / ] map ] unit-test
+[ V{ 3 2 1 } ] [ 9 get instructions>> [ ##reload? ] filter [ src>> n>> cell / ] map ] unit-test
! Resolve pass should insert this
-[ _reload ] [ 5 get predecessors>> first instructions>> first class ] unit-test
+[ ##reload ] [ 5 get predecessors>> first instructions>> first class ] unit-test
! Some random bug
V{
[ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
-[ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
+[ 0 ] [ 1 get instructions>> [ ##spill? ] count ] unit-test
-[ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
+[ 1 ] [ 2 get instructions>> [ ##spill? ] count ] unit-test
-[ 1 ] [ 3 get predecessors>> first instructions>> [ _spill? ] count ] unit-test
+[ 1 ] [ 3 get predecessors>> first instructions>> [ ##spill? ] count ] unit-test
-[ 1 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
+[ 1 ] [ 4 get instructions>> [ ##reload? ] count ] unit-test
! Another test case for fencepost error in assignment pass
V{ T{ ##branch } } 0 test-bb
[ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
-[ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
+[ 0 ] [ 1 get instructions>> [ ##spill? ] count ] unit-test
-[ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
+[ 1 ] [ 2 get instructions>> [ ##spill? ] count ] unit-test
-[ 1 ] [ 2 get instructions>> [ _reload? ] count ] unit-test
+[ 1 ] [ 2 get instructions>> [ ##reload? ] count ] unit-test
-[ 0 ] [ 3 get instructions>> [ _spill? ] count ] unit-test
+[ 0 ] [ 3 get instructions>> [ ##spill? ] count ] unit-test
-[ 0 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
+[ 0 ] [ 4 get instructions>> [ ##reload? ] count ] unit-test
USING: namespaces kernel assocs accessors sequences math math.order fry
combinators binary-search compiler.cfg.instructions compiler.cfg.registers
compiler.cfg.def-use compiler.cfg.liveness compiler.cfg.linearization.order
-compiler.cfg ;
+compiler.cfg cpu.architecture ;
IN: compiler.cfg.linear-scan.live-intervals
TUPLE: live-range from to ;
TUPLE: live-interval
vreg
reg spill-to reload-from
-start end ranges uses ;
+start end ranges uses
+reg-class ;
+
+: first-use ( live-interval -- use ) uses>> first ; inline
+
+: last-use ( live-interval -- use ) uses>> last ; inline
GENERIC: covers? ( insn# obj -- ? )
\ live-interval new
V{ } clone >>uses
V{ } clone >>ranges
+ over rep-of reg-class-of >>reg-class
swap >>vreg ;
: block-from ( bb -- n ) instructions>> first insn#>> 1 - ;
[
{
- T{ _reload { dst 1 } { rep int-rep } { src T{ spill-slot f 0 } } }
+ T{ ##reload { dst 1 } { rep int-rep } { src T{ spill-slot f 0 } } }
}
] [
[
[
{
- T{ _spill { src 1 } { rep int-rep } { dst T{ spill-slot f 0 } } }
+ T{ ##spill { src 1 } { rep int-rep } { dst T{ spill-slot f 0 } } }
}
] [
[
[
{
- T{ _spill { src 0 } { rep int-rep } { dst T{ spill-slot f 0 } } }
- T{ _reload { dst 0 } { rep tagged-rep } { src T{ spill-slot f 1 } } }
+ T{ ##spill { src 0 } { rep int-rep } { dst T{ spill-slot f 0 } } }
+ T{ ##reload { dst 0 } { rep tagged-rep } { src T{ spill-slot f 1 } } }
T{ ##branch }
}
] [
[
{
- T{ _spill { src 0 } { rep int-rep } { dst T{ spill-slot f 1 } } }
- T{ _reload { dst 0 } { rep tagged-rep } { src T{ spill-slot f 0 } } }
+ T{ ##spill { src 0 } { rep int-rep } { dst T{ spill-slot f 1 } } }
+ T{ ##reload { dst 0 } { rep tagged-rep } { src T{ spill-slot f 0 } } }
T{ ##branch }
}
] [
[
{
- T{ _spill { src 0 } { rep int-rep } { dst T{ spill-slot f 1 } } }
- T{ _reload { dst 0 } { rep tagged-rep } { src T{ spill-slot f 0 } } }
+ T{ ##spill { src 0 } { rep int-rep } { dst T{ spill-slot f 1 } } }
+ T{ ##reload { dst 0 } { rep tagged-rep } { src T{ spill-slot f 0 } } }
T{ ##branch }
}
] [
}
mapping-instructions {
{
- T{ _spill { src 0 } { rep int-rep } { dst T{ spill-slot f 8 } } }
+ T{ ##spill { src 0 } { rep int-rep } { dst T{ spill-slot f 8 } } }
T{ ##copy { dst 0 } { src 1 } { rep int-rep } }
- T{ _reload { dst 1 } { rep int-rep } { src T{ spill-slot f 8 } } }
+ T{ ##reload { dst 1 } { rep int-rep } { src T{ spill-slot f 8 } } }
T{ ##branch }
}
{
- T{ _spill { src 1 } { rep int-rep } { dst T{ spill-slot f 8 } } }
+ T{ ##spill { src 1 } { rep int-rep } { dst T{ spill-slot f 8 } } }
T{ ##copy { dst 1 } { src 0 } { rep int-rep } }
- T{ _reload { dst 0 } { rep int-rep } { src T{ spill-slot f 8 } } }
+ T{ ##reload { dst 0 } { rep int-rep } { src T{ spill-slot f 8 } } }
T{ ##branch }
}
} member?
] if ;
: memory->register ( from to -- )
- swap [ reg>> ] [ [ rep>> ] [ reg>> ] bi ] bi* _reload ;
+ swap [ reg>> ] [ [ rep>> ] [ reg>> ] bi ] bi* ##reload ;
: register->memory ( from to -- )
- [ [ reg>> ] [ rep>> ] bi ] [ reg>> ] bi* _spill ;
+ [ [ reg>> ] [ rep>> ] bi ] [ reg>> ] bi* ##spill ;
: temp->register ( from to -- )
- nip [ reg>> ] [ rep>> ] [ rep>> spill-temp ] tri _reload ;
+ nip [ reg>> ] [ rep>> ] [ rep>> spill-temp ] tri ##reload ;
: register->temp ( from to -- )
- drop [ [ reg>> ] [ rep>> ] bi ] [ rep>> spill-temp ] bi _spill ;
+ drop [ [ reg>> ] [ rep>> ] bi ] [ rep>> spill-temp ] bi ##spill ;
: register->register ( from to -- )
swap [ reg>> ] [ [ reg>> ] [ rep>> ] bi ] bi* ##copy ;
CODEGEN: ##set-vm-field %set-vm-field
CODEGEN: ##alien-global %alien-global
CODEGEN: ##call-gc %call-gc
-
+CODEGEN: ##spill %spill
+CODEGEN: ##reload %reload
CODEGEN: ##dispatch %dispatch
: %dispatch-label ( label -- )
CODEGEN: _label resolve-label
CODEGEN: _dispatch-label %dispatch-label
CODEGEN: _branch %jump-label
-CODEGEN: _spill %spill
-CODEGEN: _reload %reload
CODEGEN: _loop-entry %loop-entry
GENERIC: generate-conditional-insn ( label insn -- )