] [ drop ] if ;
: trim-before-ranges ( live-interval -- )
- [ ranges>> ] [ last-use n>> 1 + ] bi
- [ '[ from>> _ <= ] filter! drop ]
- [ swap last to<< ]
+ dup last-use n>> 1 +
+ [ '[ [ from>> _ >= ] trim-tail-slice ] change-ranges drop ]
+ [ swap ranges>> last to<< ]
2bi ;
: trim-after-ranges ( live-interval -- )
- [ ranges>> ] [ first-use n>> ] bi
- [ '[ to>> _ >= ] filter! drop ]
- [ swap first from<< ]
+ dup first-use n>>
+ [ '[ [ to>> _ < ] trim-head-slice ] change-ranges drop ]
+ [ swap ranges>> first from<< ]
2bi ;
: last-use-rep ( live-interval -- rep/f )
! Copyright (C) 2009, 2010 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays assocs combinators
+USING: accessors arrays assocs binary-search combinators
combinators.short-circuit fry hints kernel locals
-math sequences sets sorting splitting namespaces
+math math.order sequences sets sorting splitting namespaces
compiler.cfg.linear-scan.allocation.state
compiler.cfg.linear-scan.live-intervals ;
IN: compiler.cfg.linear-scan.allocation.splitting
[ split-last-range ] [ 2drop ] if
] bi ;
-: split-uses ( uses n -- before after )
- [ '[ n>> _ < ] filter ]
- [ '[ n>> _ > ] filter ]
- 2bi ;
+:: split-uses ( uses n -- before after )
+ uses n uses [ n>> <=> ] with search
+ n>> n <=> {
+ { +eq+ [ [ head-slice ] [ 1 + tail-slice ] 2bi ] }
+ { +lt+ [ 1 + cut-slice ] }
+ { +gt+ [ cut-slice ] }
+ } case ;
ERROR: splitting-too-early ;
{ 3 float-rep }
} representations set
+: clean-up-split ( a b -- a b )
+ [ dup [ [ >vector ] change-uses [ >vector ] change-ranges ] when ] bi@ ;
+
[
T{ live-interval
{ vreg 1 }
{ 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 } } }
} 2 split-for-spill
+ clean-up-split
] unit-test
[
{ 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 } } }
} 0 split-for-spill
+ clean-up-split
] unit-test
[
{ 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 } } }
} 5 split-for-spill
+ clean-up-split
] unit-test
[
{ 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 } } }
} 10 split-for-spill
+ clean-up-split
] unit-test
! Don't insert reload if first usage is a def
{ 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 } } }
} 10 split-for-spill
+ clean-up-split
] unit-test
! Multiple representations
{ 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 } } }
} 15 split-for-spill
+ clean-up-split
+] unit-test
+
+[
+ f
+ T{ live-interval
+ { vreg 7 }
+ { start 8 }
+ { 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
+ { vreg 7 }
+ { start 4 }
+ { 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
+
+! trim-before-ranges, trim-after-ranges
+[
+ T{ live-interval
+ { vreg 8 }
+ { start 0 }
+ { 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 }
+ }
+ T{ live-interval
+ { vreg 8 }
+ { start 14 }
+ { 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 }
+ }
+] [
+ T{ live-interval
+ { 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 } } }
+ { 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 }
+ } 8 split-for-spill
+ clean-up-split
] unit-test
H{
: init-live-intervals ( -- )
H{ } clone live-intervals set
V{ } clone sync-points set ;
-
+
: compute-start/end ( live-interval -- )
dup ranges>> [ first from>> ] [ last to>> ] bi
[ >>start ] [ >>end ] bi* drop ;
! to reverse some sequences, and compute the start and end.
values dup [
{
- [ ranges>> reverse! drop ]
- [ uses>> reverse! drop ]
+ [ [ { } like reverse! ] change-ranges drop ]
+ [ [ { } like reverse! ] change-uses drop ]
[ compute-start/end ]
[ check-start ]
} cleave