compiler.cfg.linear-scan.ranges: remove the live-range definition and

use integer pairs instead

so instead of ranges being a sequence of live-ranges it is now a
sequence of integer pairs instead. That makes the
compiler.cfg.linear-scan.ranges simpler and easier to generalize

diff --git a/basis/compiler/cfg/linear-scan/allocation/allocation-tests.factor b/basis/compiler/cfg/linear-scan/allocation/allocation-tests.factor
index 36bf2ca94042c26746b78b896a11ee67032c57dd..3ff3c6fa2d49a559250db7d8b383e5eb19601c1c 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/allocation-tests.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/allocation-tests.factor
@@ -9,7 +9,7 @@ IN: compiler.cfg.linear-scan.allocation.tests
     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 } }
@@ -79,9 +79,7 @@ cpu x86.64? [
                { 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 } } }
                }
@@ -90,9 +88,7 @@ cpu x86.64? [
                { 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 } } }
                }

diff --git a/basis/compiler/cfg/linear-scan/allocation/spilling/spilling-tests.factor b/basis/compiler/cfg/linear-scan/allocation/spilling/spilling-tests.factor
index d736d717c987c01f88b1a13e0307d5ec19bafdfd..d6c307e863e0c7e08fd3412157b4492ea00e252c 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/spilling/spilling-tests.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/spilling/spilling-tests.factor
@@ -13,19 +13,7 @@ IN: compiler.cfg.linear-scan.allocation.spilling.tests
        { 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
@@ -53,35 +41,24 @@ IN: compiler.cfg.linear-scan.allocation.spilling.tests
 ! 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
@@ -90,23 +67,12 @@ IN: compiler.cfg.linear-scan.allocation.spilling.tests
 ! 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

diff --git a/basis/compiler/cfg/linear-scan/allocation/splitting/splitting-tests.factor b/basis/compiler/cfg/linear-scan/allocation/splitting/splitting-tests.factor
index 9d06ce4b52aa93f8a39fc335aa0ea5168fddebed..767eea8e2fccea84ef29e7993a6e9aaed6e782ad 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/splitting/splitting-tests.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/splitting/splitting-tests.factor
@@ -5,20 +5,19 @@ IN: compiler.cfg.linear-scan.allocation.splitting.tests
 
 : 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 }
@@ -31,7 +30,7 @@ IN: compiler.cfg.linear-scan.allocation.splitting.tests
        }
     }
     T{ live-interval-state
-       { ranges { T{ live-range { from 12 } { to 20 } } } }
+       { ranges { { 12 20 } } }
        { uses
          T{ slice
             { from 1 }

diff --git a/basis/compiler/cfg/linear-scan/allocation/state/state.factor b/basis/compiler/cfg/linear-scan/allocation/state/state.factor
index 5a550b5313ebc5a1cf591e36e25ce8b77d3fb4ad..c80f7d9617adecbf25a81746400f568f115f8ab5 100644 (file)
--- a/basis/compiler/cfg/linear-scan/allocation/state/state.factor
+++ b/basis/compiler/cfg/linear-scan/allocation/state/state.factor
@@ -1,9 +1,9 @@
 ! 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
@@ -88,6 +88,9 @@ ERROR: register-already-used live-interval ;
     ! 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 {

diff --git a/basis/compiler/cfg/linear-scan/linear-scan-tests.factor b/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
index 35797ee3b9d8856b53daddfe34784d078abb7b34..e0992c0b29d231621766745b1668cbd3184e7f4d 100644 (file)
--- a/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
+++ b/basis/compiler/cfg/linear-scan/linear-scan-tests.factor
@@ -76,7 +76,7 @@ H{
        { 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 }
     }
@@ -85,7 +85,7 @@ H{
        { 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 }
     }
@@ -94,8 +94,14 @@ H{
        { 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
@@ -107,7 +113,7 @@ H{
        { 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 }
     }
@@ -116,8 +122,14 @@ H{
        { 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
@@ -128,7 +140,7 @@ H{
        { 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 }
     }
@@ -138,8 +150,14 @@ H{
        { 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
@@ -150,7 +168,7 @@ H{
        { 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 }
     }
@@ -159,7 +177,7 @@ H{
        { 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 }
     }
@@ -168,8 +186,14 @@ H{
        { 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
@@ -181,7 +205,7 @@ H{
        { 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 }
     }
@@ -190,15 +214,21 @@ H{
        { 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
@@ -210,7 +240,7 @@ H{
        { 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 }
     }
@@ -219,7 +249,7 @@ H{
        { 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 }
     }
@@ -228,8 +258,14 @@ H{
        { 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
@@ -240,7 +276,7 @@ H{
         { 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 } } }
     }
 } [
@@ -248,7 +284,7 @@ H{
         { 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
@@ -260,7 +296,7 @@ H{
         { 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 }
@@ -269,7 +305,7 @@ H{
         { 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 }
@@ -279,7 +315,7 @@ H{
         { 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 }
@@ -310,14 +346,28 @@ H{
                  { 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 }
@@ -384,7 +434,7 @@ H{ { 1 int-rep } { 2 int-rep } } representations set
            { 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" } } }
@@ -398,14 +448,14 @@ H{ { 1 int-rep } { 2 int-rep } } representations set
            { 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" } } }
@@ -419,14 +469,14 @@ H{ { 1 int-rep } { 2 int-rep } } representations set
            { 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" } } }
@@ -440,14 +490,14 @@ H{ { 1 int-rep } { 2 int-rep } } representations set
            { 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" } } }
@@ -461,14 +511,14 @@ H{ { 1 int-rep } { 2 int-rep } } representations set
            { 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" } } }
@@ -490,29 +540,41 @@ H{
            { 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
@@ -521,7 +583,7 @@ H{
            { 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" } } }
@@ -537,7 +599,7 @@ H{
            { 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
@@ -546,7 +608,7 @@ H{
            { 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" } } }
@@ -571,7 +633,7 @@ H{
                  { 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 } }
               }
 
@@ -580,7 +642,7 @@ H{
                  { 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 } }
               }
           }
@@ -594,7 +656,7 @@ H{
                  { start 0 }
                  { end 40 }
                  { reg 1 }
-                 { ranges V{ T{ live-range f 0 40 } } }
+                 { ranges V{ { 0 40 } } }
                  { uses V{ 0 40 } }
               }
           }
@@ -605,7 +667,7 @@ H{
         { 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

diff --git a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals-tests.factor b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals-tests.factor
index a97c4274e04d4182a9d4493c880007ed9f0e3657..fd1f5e661d6f8dcb9d1585baba84509350482190 100644 (file)
--- a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals-tests.factor
+++ b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals-tests.factor
@@ -40,7 +40,7 @@ IN: compiler.cfg.linear-scan.live-intervals.tests
             8
             T{ live-interval-state
                { vreg 8 }
-               { ranges V{ T{ live-range { from -10 } { to 23 } } } }
+               { ranges V{ { -10 23 } } }
                { uses V{ } }
             }
         }
@@ -48,7 +48,7 @@ IN: compiler.cfg.linear-scan.live-intervals.tests
             9
             T{ live-interval-state
                { vreg 9 }
-               { ranges V{ T{ live-range { from -10 } { to 23 } } } }
+               { ranges V{ { -10 23 } } }
                { uses V{ } }
             }
         }
@@ -56,7 +56,7 @@ IN: compiler.cfg.linear-scan.live-intervals.tests
             4
             T{ live-interval-state
                { vreg 4 }
-               { ranges V{ T{ live-range { from -10 } { to 23 } } } }
+               { ranges V{ { -10 23 } } }
                { uses V{ } }
             }
         }

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 2951844a41a988c97ca33c07f6644324361781b9..3c863577b60f38c23344b01f730e31b3483a0138 100644 (file)
--- a/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
+++ b/basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor
@@ -32,9 +32,6 @@ TUPLE: live-interval-state
     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 ;
 

diff --git a/basis/compiler/cfg/linear-scan/ranges/ranges-docs.factor b/basis/compiler/cfg/linear-scan/ranges/ranges-docs.factor
index b3130fcb17979ed7655f674e91489479bed18db2..18253b42248583787dc495aee7b3365b270c20d3 100644 (file)
--- a/basis/compiler/cfg/linear-scan/ranges/ranges-docs.factor
+++ b/basis/compiler/cfg/linear-scan/ranges/ranges-docs.factor
@@ -1,20 +1,20 @@
-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"

diff --git a/basis/compiler/cfg/linear-scan/ranges/ranges-tests.factor b/basis/compiler/cfg/linear-scan/ranges/ranges-tests.factor
index 0139f0312f1f5435c73e1d8e436b3947b34d7ff0..fa0ab4366cd6ac2a52fd5211c0350656a5aa0567 100644 (file)
--- a/basis/compiler/cfg/linear-scan/ranges/ranges-tests.factor
+++ b/basis/compiler/cfg/linear-scan/ranges/ranges-tests.factor
@@ -2,8 +2,19 @@ USING: arrays 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 ;
+! 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 } [
@@ -12,197 +23,138 @@ IN: compiler.cfg.linear-scan.ranges.tests
 
 ! 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

diff --git a/basis/compiler/cfg/linear-scan/ranges/ranges.factor b/basis/compiler/cfg/linear-scan/ranges/ranges.factor
index d108e853446f025a810edc08df455ee3a6ec254e..36e3b6f15aca53e393831dfd89a869a3ad941702 100644 (file)
--- a/basis/compiler/cfg/linear-scan/ranges/ranges.factor
+++ b/basis/compiler/cfg/linear-scan/ranges/ranges.factor
@@ -1,67 +1,61 @@
 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 ;