T{ live-interval-state
{ vreg 49 }
{ start 30 } { end 46 }
- { ranges { T{ live-range { from 30 } { to 46 } } } }
+ { ranges { { 30 46 } } }
{ uses
{
T{ vreg-use { n 30 } { def-rep double-rep } }
{ vreg 1 }
{ start 30 }
{ end 40 }
- { ranges
- { T{ live-range { from 30 } { to 40 } } }
- }
+ { ranges { { 30 40 } } }
{ uses
{ T{ vreg-use { n 32 } { def-rep double-rep } } }
}
{ vreg 50 }
{ start 5 }
{ end 10 }
- { ranges
- { T{ live-range { from 5 } { to 10 } } }
- }
+ { ranges { { 5 10 } } }
{ uses
{ T{ vreg-use { n 8 } { def-rep double-rep } } }
}
{ spill-rep double-rep }
{ start 22 }
{ end 47 }
- { ranges
- T{ slice
- { from 0 }
- { to 1 }
- { seq
- {
- T{ live-range { from 22 } { to 47 } }
- T{ live-range { from 67 } { to 68 } }
- T{ live-range { from 69 } { to 72 } }
- }
- }
- }
- }
+ { ranges { { 22 47 } { 67 68 } { 69 72 } } }
{ uses
{
T{ vreg-use
! trim-after-ranges
{
T{ live-interval-state
- { ranges
- {
- T{ live-range { from 25 } { to 30 } }
- T{ live-range { from 40 } { to 50 } }
- }
- }
+ { ranges { { 25 30 } { 40 50 } } }
{ uses { T{ vreg-use { n 25 } } } }
}
} [
T{ live-interval-state
- { ranges
- {
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 20 } { to 30 } }
- T{ live-range { from 40 } { to 50 } }
- }
- }
+ { ranges { { 0 10 } { 20 30 } { 40 50 } } }
{ uses { T{ vreg-use { n 25 } } } }
} dup trim-after-ranges
] unit-test
{
T{ live-interval-state
- { ranges { T{ live-range { from 10 } { to 23 } } } }
+ { ranges { { 10 23 } } }
{ uses { T{ vreg-use { n 10 } } } }
}
} [
T{ live-interval-state
- { ranges { T{ live-range { from 20 } { to 23 } } } }
+ { ranges { { 20 23 } } }
{ uses { T{ vreg-use { n 10 } } } }
}
dup trim-after-ranges
! trim-before-ranges
{
T{ live-interval-state
- { ranges
- {
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 20 } { to 21 } }
- }
- }
+ { ranges { { 0 10 } { 20 21 } } }
{ uses { T{ vreg-use { n 20 } } } }
}
} [
T{ live-interval-state
- { ranges
- {
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 20 } { to 30 } }
- T{ live-range { from 40 } { to 50 } }
- }
- }
+ { ranges { { 0 10 } { 20 30 } { 40 50 } } }
{ uses { T{ vreg-use { n 20 } } } }
} dup trim-before-ranges
] unit-test
: test-interval-easy ( -- interval )
T{ live-interval-state
- { ranges {
- T{ live-range { from 5 } { to 8 } }
- T{ live-range { from 12 } { to 20 } }
- } }
- { uses {
- T{ vreg-use { n 3 } { def-rep int-rep } }
- T{ vreg-use { n 15 } { def-rep int-rep } }
- } }
+ { ranges { { 5 8 } { 12 20 } } }
+ { uses
+ {
+ T{ vreg-use { n 3 } { def-rep int-rep } }
+ T{ vreg-use { n 15 } { def-rep int-rep } }
+ }
+ }
} ;
! split-interval
{
T{ live-interval-state
- { ranges { T{ live-range { from 5 } { to 8 } } } }
+ { ranges { { 5 8 } } }
{ uses
T{ slice
{ from 0 }
}
}
T{ live-interval-state
- { ranges { T{ live-range { from 12 } { to 20 } } } }
+ { ranges { { 12 20 } } }
{ uses
T{ slice
{ from 1 }
! Copyright (C) 2009, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors arrays assocs combinators compiler.cfg
-compiler.cfg.instructions
-compiler.cfg.linear-scan.live-intervals compiler.cfg.registers
-cpu.architecture fry heaps kernel math math.order namespaces sequences ;
+compiler.cfg.instructions compiler.cfg.linear-scan.live-intervals
+compiler.cfg.linear-scan.ranges compiler.cfg.registers cpu.architecture fry
+heaps kernel math math.order namespaces sequences ;
IN: compiler.cfg.linear-scan.allocation.state
SYMBOL: progress
! symbol stores an alist mapping register classes to vectors
[ get values ] dip '[ [ _ cond ] with filter! drop ] with each ; inline
+: covers? ( n live-interval -- ? )
+ ranges>> ranges-cover? ;
+
: deactivate-intervals ( n -- )
dup progress set
active-intervals {
{ start 0 }
{ end 2 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
- { ranges V{ T{ live-range f 0 2 } } }
+ { ranges V{ { 0 2 } } }
{ spill-to T{ spill-slot f 0 } }
{ spill-rep float-rep }
}
{ start 5 }
{ end 5 }
{ uses V{ T{ vreg-use f 5 f float-rep } } }
- { ranges V{ T{ live-range f 5 5 } } }
+ { ranges V{ { 5 5 } } }
{ reload-from T{ spill-slot f 0 } }
{ reload-rep float-rep }
}
{ vreg 1 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 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 }
+ }
+ }
+ { ranges V{ { 0 5 } } }
} 2 split-for-spill
clean-up-split
] unit-test
{ start 1 }
{ end 5 }
{ uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
- { ranges V{ T{ live-range f 1 5 } } }
+ { ranges V{ { 1 5 } } }
{ reload-from T{ spill-slot f 4 } }
{ reload-rep float-rep }
}
{ vreg 2 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 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 }
+ }
+ }
+ { ranges V{ { 0 5 } } }
} 0 split-for-spill
clean-up-split
] unit-test
{ start 0 }
{ end 2 }
{ uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
- { ranges V{ T{ live-range f 0 2 } } }
+ { ranges V{ { 0 2 } } }
{ spill-to T{ spill-slot f 8 } }
{ spill-rep float-rep }
}
{ vreg 3 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 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 }
+ }
+ }
+ { ranges V{ { 0 5 } } }
} 5 split-for-spill
clean-up-split
] unit-test
{ start 0 }
{ end 1 }
{ uses V{ T{ vreg-use f 0 float-rep f } } }
- { ranges V{ T{ live-range f 0 1 } } }
+ { ranges V{ { 0 1 } } }
{ spill-to T{ spill-slot f 12 } }
{ spill-rep float-rep }
}
{ start 20 }
{ end 30 }
{ uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
- { ranges V{ T{ live-range f 20 30 } } }
+ { ranges V{ { 20 30 } } }
{ reload-from T{ spill-slot f 12 } }
{ reload-rep float-rep }
}
{ vreg 4 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 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 }
+ }
+ }
+ { ranges V{ { 0 8 } { 10 18 } { 20 30 } } }
} 10 split-for-spill
clean-up-split
] unit-test
{ start 0 }
{ end 1 }
{ uses V{ T{ vreg-use f 0 float-rep f } } }
- { ranges V{ T{ live-range f 0 1 } } }
+ { ranges V{ { 0 1 } } }
{ spill-to T{ spill-slot f 16 } }
{ spill-rep float-rep }
}
{ start 20 }
{ end 30 }
{ uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
- { ranges V{ T{ live-range f 20 30 } } }
+ { 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{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
- { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 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 }
+ }
+ }
+ { ranges V{ { 0 8 } { 10 18 } { 20 30 } } }
} 10 split-for-spill
clean-up-split
] unit-test
{ 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{ T{ live-range f 0 11 } } }
+ { ranges V{ { 0 11 } } }
{ spill-to T{ spill-slot f 24 } }
{ spill-rep double-rep }
}
{ start 20 }
{ end 20 }
{ uses V{ T{ vreg-use f 20 f double-rep } } }
- { ranges V{ T{ live-range f 20 20 } } }
+ { ranges V{ { 20 20 } } }
{ reload-from T{ spill-slot f 24 } }
{ reload-rep double-rep }
}
{ vreg 6 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 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 }
+ }
+ }
+ { ranges V{ { 0 20 } } }
} 15 split-for-spill
clean-up-split
] unit-test
{ vreg 7 }
{ start 8 }
{ end 8 }
- { ranges V{ T{ live-range f 8 8 } } }
+ { ranges V{ { 8 8 } } }
{ uses V{ T{ vreg-use f 8 int-rep } } }
}
} [
{ vreg 7 }
{ start 4 }
{ end 8 }
- { ranges V{ T{ live-range f 4 8 } } }
+ { ranges V{ { 4 8 } } }
{ uses V{ T{ vreg-use f 8 int-rep } } }
} 4 split-for-spill
clean-up-split
{ vreg 8 }
{ start 0 }
{ end 3 }
- { ranges V{ T{ live-range f 0 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 } }
{ spill-rep int-rep }
{ vreg 8 }
{ start 14 }
{ end 16 }
- { ranges V{ T{ live-range f 14 16 } } }
+ { ranges V{ { 14 16 } } }
{ uses V{ T{ vreg-use f 14 f int-rep } } }
{ reload-from T{ spill-slot f 32 } }
{ reload-rep int-rep }
{ vreg 8 }
{ start 0 }
{ end 16 }
- { ranges V{ T{ live-range f 0 4 } T{ live-range f 6 10 } T{ live-range f 12 16 } } }
+ { ranges V{ { 0 4 } { 6 10 } { 12 16 } } }
{ uses
V{
T{ vreg-use f 0 f int-rep }
{ reg 1 }
{ start 1 }
{ end 15 }
- { uses V{ T{ vreg-use f 1 int-rep f } T{ vreg-use f 3 f int-rep } T{ vreg-use f 7 f int-rep } T{ vreg-use f 10 f int-rep } T{ vreg-use f 15 f int-rep } } }
+ { uses
+ V{
+ T{ vreg-use f 1 int-rep f }
+ T{ vreg-use f 3 f int-rep }
+ T{ vreg-use f 7 f int-rep }
+ T{ vreg-use f 10 f int-rep }
+ T{ vreg-use f 15 f int-rep }
+ }
+ }
}
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 4 f int-rep } T{ vreg-use f 8 f int-rep } } }
+ { uses
+ V{
+ T{ vreg-use f 3 int-rep f }
+ T{ vreg-use f 4 f int-rep }
+ T{ vreg-use f 8 f int-rep }
+ }
+ }
}
T{ live-interval-state
{ vreg 3 }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
- { ranges V{ T{ live-range f 0 100 } } }
+ { ranges V{ { 0 100 } } }
}
}
H{ { int-regs { "A" } } }
{ start 0 }
{ end 10 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
- { ranges V{ T{ live-range f 0 10 } } }
+ { 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{ T{ live-range f 11 20 } } }
+ { ranges V{ { 11 20 } } }
}
}
H{ { int-regs { "A" } } }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
- { ranges V{ T{ live-range f 0 100 } } }
+ { 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{ T{ live-range f 30 60 } } }
+ { ranges V{ { 30 60 } } }
}
}
H{ { int-regs { "A" } } }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
- { ranges V{ T{ live-range f 0 100 } } }
+ { 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{ T{ live-range f 30 200 } } }
+ { ranges V{ { 30 200 } } }
}
}
H{ { int-regs { "A" } } }
{ start 0 }
{ end 100 }
{ uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
- { ranges V{ T{ live-range f 0 100 } } }
+ { 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{ T{ live-range f 30 100 } } }
+ { ranges V{ { 30 100 } } }
}
}
H{ { int-regs { "A" } } }
{ vreg 1 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 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 }
+ }
+ }
+ { ranges V{ { 0 2 } { 10 20 } } }
}
T{ live-interval-state
{ vreg 2 }
{ 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 } } }
- { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 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 }
+ }
+ }
+ { ranges V{ { 0 2 } { 10 20 } } }
}
T{ live-interval-state
{ vreg 3 }
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 6 int-rep f } } }
- { ranges V{ T{ live-range f 4 8 } } }
+ { 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{ T{ live-range f 4 8 } } }
+ { ranges V{ { 4 8 } } }
}
! This guy will invoke the 'spill partially available' code path
{ start 4 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
- { ranges V{ T{ live-range f 4 8 } } }
+ { ranges V{ { 4 8 } } }
}
}
H{ { int-regs { "A" "B" } } }
{ 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{ T{ live-range f 0 10 } } }
+ { ranges V{ { 0 10 } } }
}
! This guy will invoke the 'spill new' code path
{ start 2 }
{ end 8 }
{ uses V{ T{ vreg-use f 8 int-rep f } } }
- { ranges V{ T{ live-range f 2 8 } } }
+ { ranges V{ { 2 8 } } }
}
}
H{ { int-regs { "A" } } }
{ start 0 }
{ end 20 }
{ reg 0 }
- { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
+ { ranges V{ { 0 2 } { 10 20 } } }
{ uses V{ 0 2 10 20 } }
}
{ start 4 }
{ end 40 }
{ reg 0 }
- { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
+ { ranges V{ { 4 6 } { 30 40 } } }
{ uses V{ 4 6 30 40 } }
}
}
{ start 0 }
{ end 40 }
{ reg 1 }
- { ranges V{ T{ live-range f 0 40 } } }
+ { ranges V{ { 0 40 } } }
{ uses V{ 0 40 } }
}
}
{ vreg 4 }
{ start 8 }
{ end 10 }
- { ranges V{ T{ live-range f 8 10 } } }
+ { ranges V{ { 8 10 } } }
{ uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
}
H{ { int-regs { 0 1 } } } register-status
8
T{ live-interval-state
{ vreg 8 }
- { ranges V{ T{ live-range { from -10 } { to 23 } } } }
+ { ranges V{ { -10 23 } } }
{ uses V{ } }
}
}
9
T{ live-interval-state
{ vreg 9 }
- { ranges V{ T{ live-range { from -10 } { to 23 } } } }
+ { ranges V{ { -10 23 } } }
{ uses V{ } }
}
}
4
T{ live-interval-state
{ vreg 4 }
- { ranges V{ T{ live-range { from -10 } { to 23 } } } }
+ { ranges V{ { -10 23 } } }
{ uses V{ } }
}
}
insn# uses last-use? [ insn# uses new-use ] unless*
spill-slot? [ t >>spill-slot? ] when ;
-: covers? ( n live-interval -- ? )
- ranges>> ranges-cover? ;
-
: (find-use) ( insn# live-interval -- vreg-use )
uses>> [ n>> <=> ] with search nip ;
-USING: compiler.cfg help.syntax help.markup math ;
+USING: arrays help.markup help.syntax math ;
IN: compiler.cfg.linear-scan.ranges
HELP: intersect-range
{ $values
- { "range1" live-range }
- { "range2" live-range }
+ { "range1" pair }
+ { "range2" pair }
{ "n/f" { $link number } " or " { $link f } }
}
{ $description "First index for the ranges intersection, or f if they don't intersect." } ;
-HELP: live-range
-{ $class-description "Represents a range in the " { $link cfg } " in which a vreg is live." } ;
-
ARTICLE: "compiler.cfg.linear-scan.ranges" "Live ranges utilities"
-"Utilities for dealing with the live range part of live intervals. A sequence of " { $link live-range } " tuples encodes where in the cfg a virtual register is live."
+"Utilities for dealing with the live range part of live intervals. A sequence of integer 2-tuples encodes the closed intervals in the cfg where a virtual register is live."
$nl
-"Constructors:" { $subsections <live-range> live-range } ;
+"Range splitting:"
+{ $subsections
+ split-range split-ranges
+} ;
ABOUT: "compiler.cfg.linear-scan.ranges"
tools.test ;
IN: compiler.cfg.linear-scan.ranges.tests
-: combine-ranges ( seq -- ranges )
- V{ } clone [ '[ first2 _ add-range ] each ] keep ;
+! add-new-range
+{
+ V{ { 10 20 } }
+} [
+ 10 20 V{ } [ add-new-range ] keep
+] unit-test
+
+! extend-ranges
+{
+ V{ { 7 25 } }
+} [
+ 7 25 V{ { 10 20 } } [ extend-ranges ] keep
+] unit-test
! extend-ranges?
{ f } [
! add-range
{
- V{ T{ live-range { from 5 } { to 12 } } }
- V{ T{ live-range { from 5 } { to 12 } } }
+ V{ { 5 12 } }
+ V{ { 5 12 } }
+ V{ { 10 12 } { 5 9 } }
} [
- { { 5 10 } { 8 12 } } combine-ranges
- { { 10 12 } { 5 10 } } combine-ranges
+ 8 12 V{ { 5 10 } } [ add-range ] keep
+ 5 10 V{ { 10 12 } } [ add-range ] keep
+
+ 5 9 V{ { 10 12 } } [ add-range ] keep
] unit-test
! intersect-range
-{ f 15 f 10 5 } [
- 10 20 <live-range> 30 40 <live-range> intersect-range
- 10 20 <live-range> 15 16 <live-range> intersect-range
- T{ live-range f 0 10 } T{ live-range f 20 30 } intersect-range
- T{ live-range f 0 10 } T{ live-range f 10 30 } intersect-range
- T{ live-range f 0 10 } T{ live-range f 5 30 } intersect-range
+{ f 15 10 5 } [
+ { 10 20 } { 30 40 } intersect-range
+ { 10 20 } { 15 16 } intersect-range
+ { 0 10 } { 10 30 } intersect-range
+ { 0 10 } { 5 30 } intersect-range
] unit-test
! intersect-ranges
{ 50 f f f 11 8 f f } [
- {
- T{ live-range f 0 10 }
- T{ live-range f 20 30 }
- T{ live-range f 40 50 }
- }
- {
- T{ live-range f 11 15 }
- T{ live-range f 31 35 }
- T{ live-range f 50 55 }
- }
- intersect-ranges
- {
- T{ live-range f 0 10 }
- T{ live-range f 20 30 }
- T{ live-range f 40 50 }
- }
- {
- T{ live-range f 11 15 }
- T{ live-range f 31 36 }
- T{ live-range f 51 55 }
- }
- intersect-ranges
- { } { T{ live-range f 11 15 } } intersect-ranges
- { T{ live-range f 11 15 } } { } intersect-ranges
- { T{ live-range f 11 15 } }
- { T{ live-range f 10 15 } T{ live-range f 16 18 } }
- intersect-ranges
- { T{ live-range f 4 20 } } { T{ live-range f 8 12 } }
- intersect-ranges
- { T{ live-range f 9 20 } T{ live-range f 3 5 } }
- { T{ live-range f 0 1 } T{ live-range f 7 8 } }
- intersect-ranges
- { T{ live-range f 3 5 } } { T{ live-range f 7 8 } } intersect-ranges
+ { { 0 10 } { 20 30 } { 40 50 } }
+ { { 11 15 } { 31 35 } { 50 55 } } intersect-ranges
+ { { 0 10 } { 20 30 } { 40 50 } }
+ { { 11 15 } { 31 36 } { 51 55 } } intersect-ranges
+ { } { { 11 15 } } intersect-ranges
+ { { 11 15 } } { } intersect-ranges
+ { { 11 15 } } { { 10 15 } { 16 18 } } intersect-ranges
+
+ { { 4 20 } } { { 8 12 } } intersect-ranges
+ { { 9 20 } { 3 5 } } { { 0 1 } { 7 8 } } intersect-ranges
+ { { 3 5 } } { { 7 8 } } intersect-ranges
] unit-test
! ranges-cover?
{
t f f t t
} [
- 115 { { 90 120 } { 40 50 } } combine-ranges ranges-cover?
- 50 { { 60 70 } { 20 30 } } combine-ranges ranges-cover?
+ 115 { { 90 120 } { 40 50 } } ranges-cover?
+ 50 { { 60 70 } { 20 30 } } ranges-cover?
120 { { 130 140 } { 70 80 } { 50 60 } { 44 48 } { 40 42 } }
- combine-ranges ranges-cover?
+ ranges-cover?
135 { { 130 140 } { 70 80 } { 50 60 } { 44 48 } }
- combine-ranges ranges-cover?
+ ranges-cover?
135 { { 130 140 } { 70 80 } { 50 60 } { 44 48 } { 40 42 } } reverse
- combine-ranges ranges-cover?
+ ranges-cover?
] unit-test
! shorten-ranges
{
- V{ T{ live-range { from 8 } { to 12 } } }
- V{ T{ live-range { from 9 } { to 9 } } }
+ V{ { 8 12 } }
+ V{ { 9 9 } }
} [
- 8 { { 4 12 } } combine-ranges [ shorten-ranges ] keep
- 9 { } combine-ranges [ shorten-ranges ] keep
+ 8 V{ { 4 12 } } [ shorten-ranges ] keep
+ 9 V{ } [ shorten-ranges ] keep
] unit-test
! split range
{
- T{ live-range f 10 15 }
- T{ live-range f 16 20 }
+ { 10 15 } { 16 20 }
} [
- 10 20 <live-range> 15 split-range
+ { 10 20 } 15 split-range
] unit-test
! split-ranges
-{
- { T{ live-range { from 10 } { to 20 } } }
- { T{ live-range { from 30 } { to 40 } } }
-} [
- 10 20 <live-range> 30 40 <live-range> 2array 25 split-ranges
-] unit-test
+{ { { 10 20 } } { { 30 40 } } }
+[ { { 10 20 } { 30 40 } } 25 split-ranges ] unit-test
-{
- { T{ live-range f 0 0 } }
- { T{ live-range f 1 5 } }
-} [
- { T{ live-range f 0 5 } } 0 split-ranges
-] unit-test
+{ { { 0 0 } } { { 1 5 } } }
+[ { { 0 5 } } 0 split-ranges ] unit-test
{
- { T{ live-range f 1 10 } T{ live-range f 15 17 } }
- { T{ live-range f 18 20 } }
+ { { 1 10 } { 15 17 } }
+ { { 18 20 } }
} [
- {
- T{ live-range f 1 10 }
- T{ live-range f 15 20 }
- } 17 split-ranges
+ { { 1 10 } { 15 20 } } 17 split-ranges
] unit-test
{
- { T{ live-range f 1 10 } }
- { T{ live-range f 15 20 } }
+ { { 1 10 } } { { 15 20 } }
} [
- {
- T{ live-range f 1 10 }
- T{ live-range f 15 20 }
- } 12 split-ranges
+ { { 1 10 } { 15 20 } } 12 split-ranges
] unit-test
{
- { T{ live-range f 1 10 } T{ live-range f 15 16 } }
- { T{ live-range f 17 20 } }
+ { { 1 10 } { 15 16 } }
+ { { 17 20 } }
} [
- {
- T{ live-range f 1 10 }
- T{ live-range f 15 20 }
- } 16 split-ranges
+ { { 1 10 } { 15 20 } } 16 split-ranges
] unit-test
{
- { T{ live-range f 1 10 } T{ live-range f 15 15 } }
- { T{ live-range f 16 20 } }
+ { { 1 10 } { 15 15 } }
+ { { 16 20 } }
} [
- {
- T{ live-range f 1 10 }
- T{ live-range f 15 20 }
- } 15 split-ranges
+ { { 1 10 } { 15 20 } } 15 split-ranges
] unit-test
[
- { T{ live-range f 1 10 } } 0 split-ranges
+ { { 1 10 } } 0 split-ranges
] must-fail
! valid-ranges?
{ t f f f } [
- { T{ live-range f 1 10 } T{ live-range f 15 20 } } valid-ranges?
- { T{ live-range f 10 1 } T{ live-range f 15 20 } } valid-ranges?
- { T{ live-range f 1 5 } T{ live-range f 3 10 } } valid-ranges?
- { T{ live-range f 5 1 } } valid-ranges?
+ { { 1 10 } { 15 20 } } valid-ranges?
+ { { 10 1 } { 15 20 } } valid-ranges?
+ { { 1 5 } { 3 10 } } valid-ranges?
+ { { 5 1 } } valid-ranges?
] unit-test
! fix-lower-bound
{
- {
- T{ live-range { from 25 } { to 30 } }
- T{ live-range { from 40 } { to 50 } }
- }
- { T{ live-range { from 10 } { to 23 } } }
+ { { 25 30 } { 40 50 } }
+ { { 10 23 } }
+ { { 366 366 } }
} [
- 25 {
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 20 } { to 30 } }
- T{ live-range { from 40 } { to 50 } }
- } fix-lower-bound
- 10 { T{ live-range { from 20 } { to 23 } } } fix-lower-bound
+ 25 { { 0 10 } { 20 30 } { 40 50 } } fix-lower-bound
+ 10 { { 20 23 } } fix-lower-bound
+ 366 { { 355 356 } { 357 366 } } fix-lower-bound
] unit-test
! fix-upper-bound
{
- {
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 20 } { to 20 } }
- }
-} [
- 20 {
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 20 } { to 30 } }
- T{ live-range { from 40 } { to 50 } }
- } fix-upper-bound
-] unit-test
-
-{
- { T{ live-range { from 0 } { to 20 } } }
+ { { 0 10 } { 20 20 } }
+ { { 0 20 } }
+ { { 0 10 } { 20 23 } }
} [
- 20 { T{ live-range { from 0 } { to 40 } } } fix-upper-bound
+ 20 { { 0 10 } { 20 30 } { 40 50 } } fix-upper-bound
+ 20 { { 0 40 } } fix-upper-bound
+ 23 { { 0 10 } { 20 30 } { 40 50 } } fix-upper-bound
] unit-test
! ranges-endpoints
{ 0 40 } [
- V{
- T{ live-range { from 0 } { to 10 } }
- T{ live-range { from 30 } { to 40 } }
- } ranges-endpoints
+ { { 0 10 } { 30 40 } } ranges-endpoints
] unit-test
USING: accessors arrays fry grouping kernel math math.order sequences ;
IN: compiler.cfg.linear-scan.ranges
-! Data definitions
-TUPLE: live-range from to ;
-
-C: <live-range> live-range
-
! Range utilities
-: intersect-range ( range1 range2 -- n/f )
- 2dup [ from>> ] bi@ > [ swap ] when
- 2dup [ to>> ] [ from>> ] bi* >=
- [ nip from>> ] [ 2drop f ] if ;
+: intersect-range ( r1 r2 -- n/f )
+ 2dup [ first ] bi@ > [ swap ] when
+ 2dup [ second ] [ first ] bi* >=
+ [ nip first ] [ 2drop f ] if ;
-: range-covers? ( n range -- ? )
- [ from>> ] [ to>> ] bi between? ;
-
-: split-range ( live-range n -- before after )
- [ [ from>> ] dip <live-range> ] [ 1 + swap to>> <live-range> ] 2bi ;
+: split-range ( range n -- before after )
+ swap first2 pick 1 + [ swap 2array ] 2bi@ ;
! Range sequence utilities
: extend-ranges? ( n ranges -- ? )
- [ drop f ] [ last from>> >= ] if-empty ;
+ [ drop f ] [ last first >= ] if-empty ;
: extend-ranges ( from to ranges -- )
- last [ max ] change-to [ min ] change-from drop ;
+ [ last first2 rot [ min ] [ max ] 2bi* 2array ] keep set-last ;
: add-new-range ( from to ranges -- )
- [ <live-range> ] dip push ;
+ [ 2array ] dip push ;
: add-range ( from to ranges -- )
2dup extend-ranges? [ extend-ranges ] [ add-new-range ] if ;
: ranges-cover? ( n ranges -- ? )
- [ range-covers? ] with any? ;
+ [ first2 between? ] with any? ;
: intersect-ranges ( ranges1 ranges2 -- n/f )
'[ _ [ intersect-range ] with map-find drop ] map-find drop ;
: shorten-ranges ( n ranges -- )
- dup empty? [ dupd add-new-range ] [ last from<< ] if ;
-
-: split-last-range? ( last n -- ? )
- swap to>> <= ;
+ dup empty? [ dupd add-new-range ] [
+ [ last second 2array ] keep set-last
+ ] if ;
: split-last-range ( before after last n -- before' after' )
split-range [ [ but-last ] dip suffix ] [ prefix ] bi-curry* bi* ;
-: split-ranges ( live-ranges n -- before after )
- [ '[ from>> _ <= ] partition ]
+: split-last-range? ( last n -- ? )
+ swap second <= ;
+
+: split-ranges ( ranges n -- before after )
+ [ '[ first _ <= ] partition ]
[
[ over last ] dip 2dup split-last-range?
[ split-last-range ] [ 2drop ] if
] bi ;
: valid-ranges? ( ranges -- ? )
- [ [ [ from>> ] [ to>> ] bi <= ] all? ]
- [ [ [ to>> ] [ from>> ] bi* <= ] monotonic? ] bi and ;
+ [ [ first2 <= ] all? ]
+ [ [ [ second ] [ first ] bi* <= ] monotonic? ] bi and ;
: fix-lower-bound ( n ranges -- ranges' )
- over '[ to>> _ >= ] filter [ first from<< ] keep ;
+ over '[ second _ >= ] filter unclip second swapd 2array prefix ;
: fix-upper-bound ( n ranges -- ranges' )
- over '[ from>> _ <= ] filter [ last to<< ] keep ;
+ over '[ first _ <= ] filter unclip-last first rot 2array suffix ;
: ranges-endpoints ( ranges -- start end )
- [ first from>> ] [ last to>> ] bi ;
+ [ first first ] [ last last ] bi ;