USING: accessors compiler.cfg compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
-compiler.cfg.linear-scan.live-intervals cpu.architecture
-cpu.x86.assembler.operands heaps kernel namespaces system tools.test ;
+compiler.cfg.linear-scan.live-intervals compiler.cfg.linear-scan.ranges
+cpu.architecture cpu.x86.assembler.operands heaps kernel namespaces system
+tools.test ;
IN: compiler.cfg.linear-scan.allocation.tests
: interval-[30,46] ( -- live-interval )
USING: assocs compiler.cfg compiler.cfg.instructions
compiler.cfg.linear-scan.allocation.spilling
compiler.cfg.linear-scan.allocation.state
-compiler.cfg.linear-scan.live-intervals compiler.cfg.registers cpu.architecture
-kernel namespaces sequences tools.test ;
+compiler.cfg.linear-scan.live-intervals compiler.cfg.linear-scan.ranges
+compiler.cfg.registers cpu.architecture kernel namespaces sequences
+tools.test ;
IN: compiler.cfg.linear-scan.allocation.spilling.tests
: test-live-interval ( -- live-interval )
USING: compiler.cfg.instructions compiler.cfg.linear-scan.allocation.splitting
-compiler.cfg.linear-scan.live-intervals cpu.architecture sequences tools.test ;
+compiler.cfg.linear-scan.live-intervals compiler.cfg.linear-scan.ranges
+cpu.architecture sequences tools.test ;
IN: compiler.cfg.linear-scan.allocation.splitting.tests
: test-interval-easy ( -- interval )
! See http://factorcode.org/license.txt for BSD license.
USING: accessors binary-search combinators
compiler.cfg.linear-scan.allocation.state
-compiler.cfg.linear-scan.live-intervals fry hints kernel locals
-math math.order namespaces sequences ;
+compiler.cfg.linear-scan.live-intervals
+compiler.cfg.linear-scan.ranges fry hints kernel locals math math.order
+namespaces sequences ;
IN: compiler.cfg.linear-scan.allocation.splitting
: split-range ( live-range n -- before after )
compiler.cfg.comparisons
compiler.cfg.ssa.destruction.leaders
compiler.cfg.linear-scan
-compiler.cfg.linear-scan.numbering
-compiler.cfg.linear-scan.live-intervals
compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
compiler.cfg.linear-scan.allocation.splitting
compiler.cfg.linear-scan.allocation.spilling
+compiler.cfg.linear-scan.live-intervals
+compiler.cfg.linear-scan.numbering
+compiler.cfg.linear-scan.ranges
compiler.cfg.linear-scan.debugger
compiler.cfg.utilities ;
IN: compiler.cfg.linear-scan.tests
USING: compiler.cfg compiler.cfg.instructions
compiler.cfg.linear-scan.allocation cpu.architecture help.markup help.syntax
-math sequences ;
+kernel math sequences ;
IN: compiler.cfg.linear-scan.live-intervals
HELP: <live-interval>
{ $values { "bb" basic-block } { "n" integer } }
{ $description "The instruction number immediately preceeding this block." } ;
+HELP: cfg>live-intervals
+{ $values { "cfg" cfg } { "live-intervals" sequence } }
+{ $description "The cfg is traversed in reverse linearization order." } ;
+
HELP: cfg>sync-points
{ $values { "cfg" cfg } { "sync-points" sequence } }
{ $description "Creates a sequence of all sync points in the cfg." }
{ $see-also sync-point } ;
+HELP: compute-live-intervals
+{ $values { "cfg" cfg } { "intervals/sync-points" sequence } }
+{ $description "Computes the live intervals and sync points of a cfg." }
+{ $notes "The instructions must be numbered." } ;
+
HELP: finish-live-intervals
{ $values { "live-intervals" sequence } }
{ $description "Since live intervals are computed in a backward order, we have to reverse some sequences, and compute the start and end." } ;
HELP: from
{ $var-description "An integer representing a sequence number one lower than all numbers in the currently processed block." } ;
+HELP: intervals-intersect?
+{ $values { "interval1" live-interval } { "interval2" live-interval } { "?" boolean } }
+{ $description "Checks if two live intervals intersect each other." } ;
+
HELP: live-interval-state
{ $class-description "A class encoding the \"liveness\" of a virtual register. It has the following slots:"
{ $table
{ "Inclusive ranges where the live interval is live. This is because the [start,end] interval can have gaps." }
}
{
- { $slot "uses" } { "sequence of references to instructions that use the register in the live interval." }
+ { $slot "uses" } { "sequence of insn# numbers which reference insructions that use the register in the live interval." }
}
{
{ $slot "reg-class" }
}
{ $notes "The " { $slot "uses" } " and " { $slot "ranges" } " will never be empty because then the interval would be unused." } ;
-
HELP: live-intervals
{ $var-description "Mapping from vreg to " { $link live-interval-state } "." } ;
-HELP: live-range
-{ $class-description "Represents a range in the " { $link cfg } " in which a vreg is live." } ;
-
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
"This vocab contains words for managing live intervals."
$nl
"Liveness classes and constructors:"
-{ $subsections
- <live-interval>
- <live-range>
- live-interval
- live-range
-} ;
+{ $subsections <live-interval> live-interval } ;
ABOUT: "compiler.cfg.linear-scan.live-intervals"
-USING: arrays compiler.cfg compiler.cfg.instructions
+USING: accessors arrays compiler.cfg compiler.cfg.instructions
compiler.cfg.linear-scan.live-intervals
-compiler.cfg.linear-scan.numbering compiler.cfg.liveness
-compiler.cfg.registers compiler.cfg.ssa.destruction.leaders
-compiler.cfg.utilities cpu.architecture kernel namespaces sequences
-tools.test ;
+compiler.cfg.linear-scan.numbering compiler.cfg.linear-scan.ranges
+compiler.cfg.liveness compiler.cfg.registers
+compiler.cfg.ssa.destruction.leaders compiler.cfg.utilities cpu.architecture
+fry kernel namespaces sequences tools.test ;
IN: compiler.cfg.linear-scan.live-intervals.tests
-! add-range
-{
- T{ live-interval-state
- { vreg 5 }
- { ranges V{ T{ live-range { from 5 } { to 12 } } } }
- { uses V{ } }
- { reg-class int-rep }
- }
-} [
- 5 int-rep <live-interval> dup
- { { 5 10 } { 8 12 } } [ first2 rot add-range ] with each
-] unit-test
-
-{
- T{ live-interval-state
- { vreg 5 }
- { ranges V{ T{ live-range { from 5 } { to 12 } } } }
- { uses V{ } }
- { reg-class int-rep }
- }
-} [
- 5 int-rep <live-interval> dup
- { { 10 12 } { 5 10 } } [ first2 rot add-range ] with each
-] unit-test
+: <live-interval-for-ranges> ( ranges -- live-interval )
+ 10 int-rep <live-interval> [ '[ first2 _ ranges>> add-range ] each ] keep
+ dup compute-start/end ;
! cfg>sync-points
{
[ number-instructions ] [ cfg>sync-points ] bi
] unit-test
+! intervals-intersect?
+{ t f f } [
+ { { 4 20 } } <live-interval-for-ranges>
+ { { 8 12 } } <live-interval-for-ranges> intervals-intersect?
+ { { 9 20 } { 3 5 } } <live-interval-for-ranges>
+ { { 0 1 } { 7 8 } } <live-interval-for-ranges> intervals-intersect?
+ { { 3 5 } } <live-interval-for-ranges>
+ { { 7 8 } } <live-interval-for-ranges> intervals-intersect?
+] unit-test
+
! handle-live-out
{ } [
H{ } clone live-outs set
! See http://factorcode.org/license.txt for BSD license.
USING: accessors assocs binary-search combinators
compiler.cfg.def-use compiler.cfg.instructions
-compiler.cfg.linearization compiler.cfg.liveness
-compiler.cfg.registers compiler.cfg.ssa.destruction.leaders cpu.architecture
-fry kernel locals math math.intervals math.order namespaces sequences ;
+compiler.cfg.linear-scan.ranges compiler.cfg.linearization
+compiler.cfg.liveness compiler.cfg.registers
+compiler.cfg.ssa.destruction.leaders cpu.architecture fry kernel locals math
+math.intervals math.order namespaces sequences ;
IN: compiler.cfg.linear-scan.live-intervals
-TUPLE: live-range from to ;
-
-C: <live-range> live-range
-
TUPLE: vreg-use n def-rep use-rep spill-slot? ;
: <vreg-use> ( n -- vreg-use ) vreg-use new swap >>n ;
TUPLE: live-interval-state
-vreg
-reg spill-to spill-rep reload-from reload-rep
-start end ranges uses
-reg-class ;
+ vreg
+ reg spill-to spill-rep reload-from reload-rep
+ start end ranges uses
+ reg-class ;
: first-use ( live-interval -- use ) uses>> first ; inline
insn# uses last-use? [ insn# uses new-use ] unless*
spill-slot? [ t >>spill-slot? ] when ;
-GENERIC: covers? ( insn# obj -- ? )
-
-M: f covers? 2drop f ;
-
-M: live-range covers? [ from>> ] [ to>> ] bi between? ;
-
-M: live-interval-state covers? ( insn# live-interval -- ? )
- ranges>>
- dup length 4 <= [
- [ covers? ] with any?
- ] [
- [ drop ] [ [ from>> <=> ] with search nip ] 2bi
- covers?
- ] if ;
+: covers? ( n live-interval -- ? )
+ ranges>> ranges-cover? ;
: (find-use) ( insn# live-interval -- vreg-use )
uses>> [ n>> <=> ] with search nip ;
insn# live-interval (find-use)
dup [ dup n>> insn# = [ drop f ] unless ] when ;
-: add-new-range ( from to live-interval -- )
- [ <live-range> ] dip ranges>> push ;
-
-: shorten-range ( n live-interval -- )
- dup ranges>> empty?
- [ dupd add-new-range ] [ ranges>> last from<< ] if ;
-
-: extend-range ( from to live-range -- )
- ranges>> last
- [ max ] change-to
- [ min ] change-from
- drop ;
-
-: extend-range? ( to live-interval -- ? )
- ranges>> [ drop f ] [ last from>> >= ] if-empty ;
-
-: add-range ( from to live-interval -- )
- 2dup extend-range?
- [ extend-range ] [ add-new-range ] if ;
-
: <live-interval> ( vreg reg-class -- live-interval )
\ live-interval-state new
V{ } clone >>uses
:: record-def ( vreg n spill-slot? -- )
vreg live-interval :> live-interval
- n live-interval shorten-range
+ n live-interval ranges>> shorten-ranges
n live-interval spill-slot? (add-use) vreg rep-of >>def-rep drop ;
:: record-use ( vreg n spill-slot? -- )
vreg live-interval :> live-interval
- from get n live-interval add-range
+ from get n live-interval ranges>> add-range
n live-interval spill-slot? (add-use) vreg rep-of >>use-rep drop ;
:: record-temp ( vreg n -- )
vreg live-interval :> live-interval
- n n live-interval add-range
+ n n live-interval ranges>> add-range
n live-interval f (add-use) vreg rep-of >>def-rep drop ;
M: vreg-insn compute-live-intervals* ( insn -- )
: handle-live-out ( bb -- )
[ from get to get ] dip live-out keys
- [ live-interval add-range ] 2with each ;
+ [ live-interval ranges>> add-range ] 2with each ;
: compute-live-intervals-step ( bb -- )
{
--- /dev/null
+USING: compiler.cfg help.syntax help.markup ;
+IN: compiler.cfg.linear-scan.ranges
+
+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."
+$nl
+"Constructors:" { $subsections <live-range> live-range } ;
+
+ABOUT: "compiler.cfg.linear-scan.ranges"
--- /dev/null
+USING: compiler.cfg.linear-scan.ranges fry kernel sequences tools.test ;
+IN: compiler.cfg.linear-scan.ranges.tests
+
+: combine-ranges ( seq -- ranges )
+ V{ } clone [ '[ first2 _ add-range ] each ] keep ;
+
+! extend-ranges?
+{ f } [
+ 10 { } extend-ranges?
+] unit-test
+
+! add-range
+{
+ V{ T{ live-range { from 5 } { to 12 } } }
+ V{ T{ live-range { from 5 } { to 12 } } }
+} [
+ { { 5 10 } { 8 12 } } combine-ranges
+ { { 10 12 } { 5 10 } } combine-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?
+ 120 { { 130 140 } { 70 80 } { 50 60 } { 44 48 } { 40 42 } }
+ combine-ranges ranges-cover?
+ 135 { { 130 140 } { 70 80 } { 50 60 } { 44 48 } }
+ combine-ranges ranges-cover?
+ 135 { { 130 140 } { 70 80 } { 50 60 } { 44 48 } { 40 42 } } reverse
+ combine-ranges ranges-cover?
+] unit-test
+
+! shorten-ranges
+{
+ V{ T{ live-range { from 8 } { to 12 } } }
+ V{ T{ live-range { from 9 } { to 9 } } }
+} [
+ 8 { { 4 12 } } combine-ranges [ shorten-ranges ] keep
+ 9 { } combine-ranges [ shorten-ranges ] keep
+] unit-test
--- /dev/null
+USING: accessors 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
+: range-covers? ( n range -- ? )
+ [ from>> ] [ to>> ] bi between? ;
+
+! Range sequence utilities
+: extend-ranges? ( n ranges -- ? )
+ [ drop f ] [ last from>> >= ] if-empty ;
+
+: extend-ranges ( from to ranges -- )
+ last [ max ] change-to [ min ] change-from drop ;
+
+: add-new-range ( from to ranges -- )
+ [ <live-range> ] dip push ;
+
+: add-range ( from to ranges -- )
+ 2dup extend-ranges? [ extend-ranges ] [ add-new-range ] if ;
+
+: ranges-cover? ( n ranges -- ? )
+ [ range-covers? ] with any? ;
+
+: shorten-ranges ( n ranges -- )
+ dup empty? [ dupd add-new-range ] [ last from<< ] if ;