compiler.cfg.linear-scan: pointless optimizations

diff --git a/basis/compiler/cfg/linear-scan/allocation/spilling/spilling.factor b/basis/compiler/cfg/linear-scan/allocation/spilling/spilling.factor
index be5ab9d48169da77bbe2ff97d12dca320206982a..e773cb9e46e98606db812337e23c6f4e8981fe6f 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/spilling/spilling.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/spilling/spilling.factor
@@ -17,15 +17,15 @@ ERROR: bad-live-ranges interval ;
     ] [ 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 )

diff --git a/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor b/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor
index e3959906d2aad2afbc5875a1f881a2d2336c52a5..0430bfef85ed870b2c0e4c097294c56499727e36 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor
@@ -1,8 +1,8 @@
 ! 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
@@ -25,10 +25,13 @@ 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 ;
 

diff --git a/basis/compiler/cfg/linear-scan/linear-scan-tests.factor b/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
index 60976eb30593d56fa7c90e9356ecb80661970f33..c6252c2ea6a6021e81edf0fe2a3a4ae180b11757 100644 (file)
--- a/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
+++ b/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
@@ -85,6 +85,9 @@ H{
     { 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 }
@@ -115,6 +118,7 @@ H{
        { 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
 
 [
@@ -138,6 +142,7 @@ H{
        { 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
 
 [
@@ -161,6 +166,7 @@ H{
        { 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
 
 [
@@ -193,6 +199,7 @@ H{
        { 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
@@ -224,6 +231,7 @@ H{
        { 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
@@ -257,6 +265,63 @@ H{
        { 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{

diff --git a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
index 3dd9e5a6dbd8761ad77d90f5b3c538ad8540b941..d874d0b5fbdfd42814581d070ed48a9b04effec8 100644 (file)
--- a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
+++ b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
@@ -165,7 +165,7 @@ M: insn compute-sync-points* drop ;
 : 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 ;
@@ -180,8 +180,8 @@ ERROR: bad-live-interval live-interval ;
     ! 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