USING: accessors compiler.cfg compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
compiler.cfg.linear-scan.live-intervals compiler.cfg.linear-scan.ranges
-cpu.architecture cpu.x86.assembler.operands heaps kernel namespaces system
-tools.test ;
+compiler.cfg.registers cpu.architecture cpu.x86.assembler.operands heaps kernel
+namespaces system tools.test ;
IN: compiler.cfg.linear-scan.allocation.tests
: interval-[30,46] ( -- live-interval )
T{ vreg-use { n 46 } { use-rep double-rep } }
}
}
- { reg-class int-regs }
} clone ;
: interval-[30,60] ( -- live-interval )
T{ live-interval-state
{ vreg 25 }
{ start 30 } { end 60 }
- { reg-class int-regs }
{ reg RAX }
} ;
cpu x86.64? [
! assign-registers
{ RAX } [
+ H{ { 49 int-rep } } representations set
f machine-registers init-allocator
interval-[30,46] dup machine-registers assign-register reg>>
] unit-test
{ { RBX 1/0. } } [
f machine-registers init-allocator
+ H{ { 25 int-rep } { 49 int-rep } } representations set
interval-[30,60] add-active
interval-[30,46] machine-registers register-status
] unit-test
of [ 1/0. 2array ] map ;
: register-status ( new registers -- free-pos )
- over reg-class>> free-positions [
+ over interval-reg-class free-positions [
[ inactive-positions ] [ active-positions ] 2bi
] keep alist-max ;
USING: accessors assocs combinators.extras compiler.cfg
compiler.cfg.instructions compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
-compiler.cfg.linear-scan.live-intervals compiler.cfg.utilities
-cpu.architecture cpu.x86.assembler.operands heaps kernel layouts
-literals namespaces sequences system tools.test ;
+compiler.cfg.linear-scan.live-intervals compiler.cfg.registers
+compiler.cfg.utilities cpu.architecture cpu.x86.assembler.operands heaps
+kernel layouts literals namespaces sequences system tools.test ;
IN: compiler.cfg.linear-scan.allocation.state.tests
! active-intervals-for
{
- V{ T{ live-interval-state { reg-class int-regs } { vreg 123 } } }
+ V{ T{ live-interval-state { vreg 123 } } }
} [
f machine-registers init-allocator
- T{ live-interval-state { reg-class int-regs } { vreg 123 } }
+ H{ { 123 int-rep } } representations set
+ T{ live-interval-state { vreg 123 } }
[ add-active ] keep active-intervals-for
] unit-test
V{
T{ live-interval-state
{ vreg 123 }
- { reg-class int-regs }
}
}
}
}
} [
f machine-registers init-allocator
- T{ live-interval-state { reg-class int-regs } { vreg 123 } } add-active
+ H{ { 123 int-rep } } representations set
+ T{ live-interval-state { vreg 123 } } add-active
active-intervals get
] unit-test
40 progress set
T{ live-interval-state
{ end 34 }
- { reg-class int-regs }
{ vreg 123 }
}
check-handled
! inactive-intervals-for
{
- V{ T{ live-interval-state { reg-class int-regs } { vreg 123 } } }
+ V{ T{ live-interval-state { vreg 123 } } }
} [
f machine-registers init-allocator
- T{ live-interval-state { reg-class int-regs } { vreg 123 } }
+ H{ { 123 int-rep } } representations set
+ T{ live-interval-state { vreg 123 } }
[ add-inactive ] keep inactive-intervals-for
] unit-test
SYMBOL: active-intervals
: active-intervals-for ( live-interval -- seq )
- reg-class>> active-intervals get at ;
+ interval-reg-class active-intervals get at ;
: add-active ( live-interval -- )
dup active-intervals-for push ;
SYMBOL: inactive-intervals
: inactive-intervals-for ( live-interval -- seq )
- reg-class>> inactive-intervals get at ;
+ interval-reg-class inactive-intervals get at ;
: add-inactive ( live-interval -- )
dup inactive-intervals-for push ;
{ V{ T{ ##spill { src RAX } { rep int-rep } } } } [
[
- 1234 int-regs <live-interval>
+ 1234 <live-interval>
RAX >>reg int-rep >>spill-rep
insert-spill
] V{ } make
] unit-test
{ 3 } [
- { 50 90 95 120 } [ 25 int-regs <live-interval> 2array ] map >min-heap
+ { 50 90 95 120 } [ 25 <live-interval> 2array ] map >min-heap
pending-interval-heap set 90 expire-old-intervals
pending-interval-heap get heap-size
] unit-test
{
T{ live-interval-state
{ vreg 1 }
- { reg-class float-regs }
{ start 0 }
{ end 2 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
}
T{ live-interval-state
{ vreg 1 }
- { reg-class float-regs }
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 f float-rep } } }
} [
T{ live-interval-state
{ vreg 1 }
- { reg-class float-regs }
{ start 0 }
{ end 5 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
f
T{ live-interval-state
{ vreg 2 }
- { reg-class float-regs }
{ start 1 }
{ end 5 }
{ uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
} [
T{ live-interval-state
{ vreg 2 }
- { reg-class float-regs }
{ start 0 }
{ end 5 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
{
T{ live-interval-state
{ vreg 3 }
- { reg-class float-regs }
{ start 0 }
{ end 2 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
} [
T{ live-interval-state
{ vreg 3 }
- { reg-class float-regs }
{ start 0 }
{ end 5 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
{
T{ live-interval-state
{ vreg 4 }
- { reg-class float-regs }
{ start 0 }
{ end 1 }
{ uses V{ T{ vreg-use f 0 float-rep f } } }
}
T{ live-interval-state
{ vreg 4 }
- { reg-class float-regs }
{ start 20 }
{ end 30 }
{ uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
} [
T{ live-interval-state
{ vreg 4 }
- { reg-class float-regs }
{ start 0 }
{ end 30 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
{
T{ live-interval-state
{ vreg 5 }
- { reg-class float-regs }
{ start 0 }
{ end 1 }
{ uses V{ T{ vreg-use f 0 float-rep f } } }
}
T{ live-interval-state
{ vreg 5 }
- { reg-class float-regs }
{ start 20 }
{ end 30 }
{ uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
} [
T{ live-interval-state
{ vreg 5 }
- { reg-class float-regs }
{ start 0 }
{ end 30 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
{
T{ live-interval-state
{ vreg 6 }
- { reg-class float-regs }
{ start 0 }
{ end 11 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
}
T{ live-interval-state
{ vreg 6 }
- { reg-class float-regs }
{ start 20 }
{ end 20 }
{ uses V{ T{ vreg-use f 20 f double-rep } } }
} [
T{ live-interval-state
{ vreg 6 }
- { reg-class float-regs }
{ start 0 }
{ end 20 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } T{ vreg-use f 20 f double-rep } } }
{ end 8 }
{ ranges V{ T{ live-range f 8 8 } } }
{ uses V{ T{ vreg-use f 8 int-rep } } }
- { reg-class int-regs }
}
} [
T{ live-interval-state
{ end 8 }
{ ranges V{ T{ live-range f 4 8 } } }
{ uses V{ T{ vreg-use f 8 int-rep } } }
- { reg-class int-regs }
} 4 split-for-spill
clean-up-split
] unit-test
{ end 3 }
{ ranges V{ T{ live-range f 0 3 } } }
{ uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
- { reg-class int-regs }
{ spill-to T{ spill-slot f 32 } }
{ spill-rep int-rep }
}
{ end 16 }
{ ranges V{ T{ live-range f 14 16 } } }
{ uses V{ T{ vreg-use f 14 f int-rep } } }
- { reg-class int-regs }
{ reload-from T{ spill-slot f 32 } }
{ reload-rep int-rep }
}
{ start 0 }
{ end 16 }
{ ranges V{ T{ live-range f 0 4 } T{ live-range f 6 10 } T{ live-range f 12 16 } } }
- { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } T{ vreg-use f 14 f int-rep } } }
- { reg-class int-regs }
+ { uses
+ V{
+ T{ vreg-use f 0 f int-rep }
+ T{ vreg-use f 2 f int-rep }
+ T{ vreg-use f 14 f int-rep } }
+ }
} 8 split-for-spill
clean-up-split
] unit-test
V{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ reg 1 }
{ start 1 }
{ end 15 }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ reg 2 }
{ start 3 }
{ end 8 }
}
T{ live-interval-state
{ vreg 3 }
- { reg-class int-regs }
{ reg 3 }
{ start 3 }
{ end 10 }
H{ } inactive-intervals set
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 int-rep f } } }
V{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ reg 1 }
{ start 1 }
{ end 15 }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ reg 2 }
{ start 3 }
{ end 8 }
H{ } inactive-intervals set
T{ live-interval-state
{ vreg 3 }
- { reg-class int-regs }
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 int-rep f } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 10 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ start 11 }
{ end 20 }
{ uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ start 30 }
{ end 60 }
{ uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ start 30 }
{ end 200 }
{ uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ start 30 }
{ end 100 }
{ uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 20 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } T{ vreg-use f 20 f int-rep } } }
}
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ start 0 }
{ end 20 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } T{ vreg-use f 20 f int-rep } } }
}
T{ live-interval-state
{ vreg 3 }
- { reg-class int-regs }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 6 int-rep f } } }
}
T{ live-interval-state
{ vreg 4 }
- { reg-class int-regs }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
! This guy will invoke the 'spill partially available' code path
T{ live-interval-state
{ vreg 5 }
- { reg-class int-regs }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ 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 } } }
! This guy will invoke the 'spill new' code path
T{ live-interval-state
{ vreg 5 }
- { reg-class int-regs }
{ start 2 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
{
T{ live-interval-state
{ vreg 1 }
- { reg-class int-regs }
{ start 0 }
{ end 20 }
{ reg 0 }
T{ live-interval-state
{ vreg 2 }
- { reg-class int-regs }
{ start 4 }
{ end 40 }
{ reg 0 }
{
T{ live-interval-state
{ vreg 3 }
- { reg-class int-regs }
{ start 0 }
{ end 40 }
{ reg 1 }
T{ live-interval-state
{ vreg 4 }
- { reg-class int-regs }
{ start 8 }
{ end 10 }
{ ranges V{ T{ live-range f 8 10 } } }
HELP: <live-interval>
{ $values
{ "vreg" "virtual register" }
- { "reg-class" "register class" }
{ "live-interval" live-interval-state }
}
{ $description "Creates a new live interval for a virtual register. Initially the range is empty." } ;
HELP: live-intervals
{ $var-description "Mapping from vreg to " { $link live-interval-state } "." } ;
+HELP: record-temp
+{ $values { "vreg" number } { "n" number } }
+{ $description "Assigns the interval [n,n] to vreg:s live interval." } ;
+
HELP: sync-point
{ $class-description "A location where all registers have to be spilled. For example when garbage collection is run or an alien ffi call is invoked. Figuring out where in the " { $link cfg } " the sync points are is done in the " { $link compute-live-intervals } " step. The tuple has the following slots:"
{ $table
IN: compiler.cfg.linear-scan.live-intervals.tests
: <live-interval-for-ranges> ( ranges -- live-interval )
- 10 int-rep <live-interval> [ '[ first2 _ ranges>> add-range ] each ] keep
+ 10 <live-interval> [ '[ first2 _ ranges>> add-range ] each ] keep
dup compute-start/end ;
! cfg>sync-points
{ vreg 8 }
{ ranges V{ T{ live-range { from -10 } { to 23 } } } }
{ uses V{ } }
- { reg-class int-regs }
}
}
{
{ vreg 9 }
{ ranges V{ T{ live-range { from -10 } { to 23 } } } }
{ uses V{ } }
- { reg-class int-regs }
}
}
{
{ vreg 4 }
{ ranges V{ T{ live-range { from -10 } { to 23 } } } }
{ uses V{ } }
- { reg-class int-regs }
}
}
}
} [
T{ live-interval-state
{ start 0 }
- { reg-class int-regs }
{ end 10 }
{ uses { 0 10 } }
{ ranges V{ T{ live-range f 0 10 } } }
}
T{ live-interval-state
{ start 5 }
- { reg-class int-regs }
{ end 10 }
{ uses { 5 10 } }
{ ranges V{ T{ live-range f 5 10 } } }
TUPLE: live-interval-state
vreg
reg spill-to spill-rep reload-from reload-rep
- start end ranges uses
- reg-class ;
+ start end ranges uses ;
: first-use ( live-interval -- use ) uses>> first ; inline
insn# live-interval (find-use)
dup [ dup n>> insn# = [ drop f ] unless ] when ;
-: <live-interval> ( vreg reg-class -- live-interval )
+: <live-interval> ( vreg -- live-interval )
\ live-interval-state new
V{ } clone >>uses
V{ } clone >>ranges
- swap >>reg-class
swap >>vreg ;
: block-from ( bb -- n ) instructions>> first insn#>> 1 - ;
SYMBOL: live-intervals
: live-interval ( vreg -- live-interval )
- leader live-intervals get
- [ dup rep-of reg-class-of <live-interval> ] cache ;
+ leader live-intervals get [ <live-interval> ] cache ;
+
+: interval-reg-class ( live-interval -- reg-class )
+ vreg>> rep-of reg-class-of ;
GENERIC: compute-live-intervals* ( insn -- )