compiler.cfg.liveness: merge in compiler.cfg.liveness.ssa and simplify the code,...

diff --git a/basis/compiler/cfg/linear-scan/assignment/assignment.factor b/basis/compiler/cfg/linear-scan/assignment/assignment.factor
index 365d4e2f21382a1715edb7392fb3efeb571fbb6a..9a66307a93eed5f58bccaec9aa5d276197c6771b 100644 (file)
--- a/basis/compiler/cfg/linear-scan/assignment/assignment.factor
+++ b/basis/compiler/cfg/linear-scan/assignment/assignment.factor
@@ -6,7 +6,6 @@ cpu.architecture layouts
 compiler.cfg
 compiler.cfg.def-use
 compiler.cfg.liveness
-compiler.cfg.liveness.ssa
 compiler.cfg.registers
 compiler.cfg.instructions
 compiler.cfg.linearization

diff --git a/basis/compiler/cfg/liveness/liveness-tests.factor b/basis/compiler/cfg/liveness/liveness-tests.factor
index 7099d3a06ecddc35cd280d4b8cd1805826ba7bc9..a6bd82183a704a508d0d24742696e7b03934ba46 100644 (file)
--- a/basis/compiler/cfg/liveness/liveness-tests.factor
+++ b/basis/compiler/cfg/liveness/liveness-tests.factor
@@ -1,19 +1,15 @@
-USING: compiler.cfg.liveness compiler.cfg.liveness.ssa
+USING: compiler.cfg.liveness
 compiler.cfg.debugger compiler.cfg.instructions
 compiler.cfg.predecessors compiler.cfg.registers compiler.cfg
 cpu.architecture accessors namespaces sequences kernel
 tools.test vectors alien math compiler.cfg.comparisons
-cpu.x86.assembler.operands ;
+cpu.x86.assembler.operands assocs ;
 IN: compiler.cfg.liveness.tests
 
 : test-liveness ( -- )
     cfg new 1 get >>entry
     compute-live-sets ;
 
-: test-ssa-liveness ( -- )
-    cfg new 1 get >>entry
-    compute-ssa-live-sets ;
-
 ! Sanity check...
 
 V{
@@ -148,9 +144,65 @@ V{
 7 8 edge
 8 9 edge
 
-[ ] [ test-ssa-liveness ] unit-test
+[ ] [ test-liveness ] unit-test
 
 [ H{ { 28 28 } { 29 29 } { 30 30 } { 31 31 } } ] [ 5 get live-out ] unit-test
 [ H{ { 28 28 } { 29 29 } { 30 30 } } ] [ 6 get live-in ] unit-test
 [ H{ { 28 28 } { 29 29 } { 31 31 } } ] [ 7 get live-in ] unit-test
-[ H{ { 30 30 } } ] [ 6 get 8 get edge-live-in ] unit-test
\ No newline at end of file
+[ H{ { 30 30 } } ] [ 6 get 8 get edge-live-in ] unit-test
+
+V{
+    T{ ##prologue }
+    T{ ##branch }
+} 0 test-bb
+
+V{
+    T{ ##branch }
+} 1 test-bb
+
+V{
+    T{ ##load-integer f 0 0 }
+    T{ ##branch }
+} 2 test-bb
+
+V{
+    T{ ##load-integer f 1 1 }
+    T{ ##branch }
+} 3 test-bb
+
+V{
+    T{ ##phi f 2 H{ { 2 0 } { 3 1 } } }
+    T{ ##branch }
+} 4 test-bb
+
+V{
+    T{ ##branch }
+} 5 test-bb
+
+V{
+    T{ ##replace f 2 D 0 }
+    T{ ##branch }
+} 6 test-bb
+
+V{
+    T{ ##epilogue }
+    T{ ##return }
+} 7 test-bb
+
+0 1 edge
+1 { 2 3 } edges
+2 4 edge
+3 4 edge
+4 { 5 6 } edges
+5 6 edge
+6 7 edge
+
+[ ] [ cfg new 0 get >>entry dup cfg set compute-live-sets ] unit-test
+
+[ t ] [ 0 get live-in assoc-empty? ] unit-test
+
+[ H{ { 2 2 } } ] [ 4 get live-out ] unit-test
+
+[ H{ { 0 0 } } ] [ 2 get 4 get edge-live-in ] unit-test
+
+[ H{ { 1 1 } } ] [ 3 get 4 get edge-live-in ] unit-test
\ No newline at end of file

diff --git a/basis/compiler/cfg/liveness/liveness.factor b/basis/compiler/cfg/liveness/liveness.factor
index cbf41053927ef007b7ae46bd35b2caece927e810..25d78a8d8fea7433ab8c8d71825f5797c7711bd9 100644 (file)
--- a/basis/compiler/cfg/liveness/liveness.factor
+++ b/basis/compiler/cfg/liveness/liveness.factor
@@ -1,17 +1,31 @@
 ! Copyright (C) 2009, 2010 Slava Pestov.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: kernel accessors assocs namespaces sequences sets
-compiler.cfg.def-use compiler.cfg.dataflow-analysis
+USING: kernel accessors assocs fry deques dlists namespaces
+sequences sets compiler.cfg compiler.cfg.def-use
 compiler.cfg.instructions compiler.cfg.registers
-cpu.architecture ;
+compiler.cfg.utilities compiler.cfg.predecessors
+compiler.cfg.rpo cpu.architecture ;
+FROM: namespaces => set ;
 IN: compiler.cfg.liveness
 
 ! See http://en.wikipedia.org/wiki/Liveness_analysis
-! Do not run after SSA construction; compiler.cfg.liveness.ssa
-! should be used instead. The transfer-liveness word is used
-! by SSA liveness too, so it handles ##phi instructions.
 
-BACKWARD-ANALYSIS: live
+SYMBOL: live-ins
+
+: live-in ( bb -- set )
+    live-ins get at ;
+
+SYMBOL: live-outs
+
+: live-out ( bb -- set )
+    live-outs get at ;
+
+! Assoc mapping basic blocks to sequences of sets of vregs; each
+! sequence is in correspondence with a predecessor
+SYMBOL: edge-live-ins
+
+: edge-live-in ( predecessor basic-block -- set )
+    edge-live-ins get at at ;
 
 GENERIC: visit-insn ( live-set insn -- live-set )
 
@@ -23,6 +37,11 @@ GENERIC: visit-insn ( live-set insn -- live-set )
 
 M: vreg-insn visit-insn [ kill-defs ] [ gen-uses ] bi ;
 
+! Our liveness analysis annotates call sites with GC maps
+! indicating the spill slots in the stack frame that contain
+! tagged pointers, and thus have to be visited if a GC occurs
+! inside the call.
+
 : fill-gc-map ( live-set insn -- live-set )
     representations get [
         gc-map>> over keys
@@ -44,8 +63,49 @@ M: insn visit-insn drop ;
 : local-live-in ( instructions -- live-set )
     [ H{ } ] dip transfer-liveness keys ;
 
-M: live-analysis transfer-set
-    drop instructions>> transfer-liveness ;
+SYMBOL: work-list
+
+: add-to-work-list ( basic-blocks -- )
+    work-list get '[ _ push-front ] each ;
+
+: compute-live-in ( basic-block -- live-in )
+    [ live-out ] keep instructions>> transfer-liveness ;
+
+: compute-edge-live-in ( basic-block -- edge-live-in )
+    H{ } clone [
+        '[ inputs>> [ swap _ conjoin-at ] assoc-each ] each-phi
+    ] keep ;
+
+: update-live-in ( basic-block -- changed? )
+    [ [ compute-live-in ] keep live-ins get maybe-set-at ]
+    [ [ compute-edge-live-in ] keep edge-live-ins get maybe-set-at ]
+    bi or ;
+
+: compute-live-out ( basic-block -- live-out )
+    [ successors>> [ live-in ] map ]
+    [ dup successors>> [ edge-live-in ] with map ] bi
+    append assoc-combine ;
+
+: update-live-out ( basic-block -- changed? )
+    [ compute-live-out ] keep
+    live-outs get maybe-set-at ;
+
+: liveness-step ( basic-block -- )
+    dup update-live-out [
+        dup update-live-in
+        [ predecessors>> add-to-work-list ] [ drop ] if
+    ] [ drop ] if ;
+
+: compute-live-sets ( cfg -- )
+    needs-predecessors
+
+    <hashed-dlist> work-list set
+    H{ } clone live-ins set
+    H{ } clone edge-live-ins set
+    H{ } clone live-outs set
+    post-order add-to-work-list
+    work-list get [ liveness-step ] slurp-deque ;
+
+: live-in? ( vreg bb -- ? ) live-in key? ;
 
-M: live-analysis join-sets
-    2drop assoc-combine ;
+: live-out? ( vreg bb -- ? ) live-out key? ;

diff --git a/basis/compiler/cfg/liveness/ssa/ssa-tests.factor b/basis/compiler/cfg/liveness/ssa/ssa-tests.factor
deleted file mode 100644 (file)
index 5413c65..0000000
--- a/basis/compiler/cfg/liveness/ssa/ssa-tests.factor
+++ /dev/null
@@ -1,61 +0,0 @@
-USING: accessors compiler.cfg compiler.cfg.debugger
-compiler.cfg.instructions compiler.cfg.liveness.ssa
-compiler.cfg.liveness arrays sequences assocs
-compiler.cfg.registers kernel namespaces tools.test ;
-IN: compiler.cfg.liveness.ssa.tests
-
-V{
-    T{ ##prologue }
-    T{ ##branch }
-} 0 test-bb
-
-V{
-    T{ ##branch }
-} 1 test-bb
-
-V{
-    T{ ##load-integer f 0 0 }
-    T{ ##branch }
-} 2 test-bb
-
-V{
-    T{ ##load-integer f 1 1 }
-    T{ ##branch }
-} 3 test-bb
-
-V{
-    T{ ##phi f 2 H{ { 2 0 } { 3 1 } } }
-    T{ ##branch }
-} 4 test-bb
-
-V{
-    T{ ##branch }
-} 5 test-bb
-
-V{
-    T{ ##replace f 2 D 0 }
-    T{ ##branch }
-} 6 test-bb
-
-V{
-    T{ ##epilogue }
-    T{ ##return }
-} 7 test-bb
-
-0 1 edge
-1 { 2 3 } edges
-2 4 edge
-3 4 edge
-4 { 5 6 } edges
-5 6 edge
-6 7 edge
-
-[ ] [ cfg new 0 get >>entry dup cfg set compute-ssa-live-sets ] unit-test
-
-[ t ] [ 0 get live-in assoc-empty? ] unit-test
-
-[ H{ { 2 2 } } ] [ 4 get live-out ] unit-test
-
-[ H{ { 0 0 } } ] [ 2 get 4 get edge-live-in ] unit-test
-
-[ H{ { 1 1 } } ] [ 3 get 4 get edge-live-in ] unit-test

diff --git a/basis/compiler/cfg/liveness/ssa/ssa.factor b/basis/compiler/cfg/liveness/ssa/ssa.factor
deleted file mode 100644 (file)
index 8442851..0000000
--- a/basis/compiler/cfg/liveness/ssa/ssa.factor
+++ /dev/null
@@ -1,63 +0,0 @@
-! Copyright (C) 2009, 2010 Slava Pestov.
-! See http://factorcode.org/license.txt for BSD license.
-USING: kernel namespaces deques accessors sets sequences assocs fry
-hashtables dlists compiler.cfg.def-use compiler.cfg.instructions
-compiler.cfg.rpo compiler.cfg.liveness compiler.cfg.utilities
-compiler.cfg.predecessors ;
-FROM: namespaces => set ;
-IN: compiler.cfg.liveness.ssa
-
-! TODO: merge with compiler.cfg.liveness
-
-! Assoc mapping basic blocks to sequences of sets of vregs; each sequence
-! is in correspondence with a predecessor
-SYMBOL: edge-live-ins
-
-: edge-live-in ( predecessor basic-block -- set ) edge-live-ins get at at ;
-
-SYMBOL: work-list
-
-: add-to-work-list ( basic-blocks -- )
-    work-list get '[ _ push-front ] each ;
-
-: compute-live-in ( basic-block -- live-in )
-    [ live-out ] keep instructions>> transfer-liveness ;
-
-: compute-edge-live-in ( basic-block -- edge-live-in )
-    H{ } clone [
-        '[ inputs>> [ swap _ conjoin-at ] assoc-each ] each-phi
-    ] keep ;
-
-: update-live-in ( basic-block -- changed? )
-    [ [ compute-live-in ] keep live-ins get maybe-set-at ]
-    [ [ compute-edge-live-in ] keep edge-live-ins get maybe-set-at ]
-    bi or ;
-
-: compute-live-out ( basic-block -- live-out )
-    [ successors>> [ live-in ] map ]
-    [ dup successors>> [ edge-live-in ] with map ] bi
-    append assoc-combine ;
-
-: update-live-out ( basic-block -- changed? )
-    [ compute-live-out ] keep
-    live-outs get maybe-set-at ;
-
-: liveness-step ( basic-block -- )
-    dup update-live-out [
-        dup update-live-in
-        [ predecessors>> add-to-work-list ] [ drop ] if
-    ] [ drop ] if ;
-
-: compute-ssa-live-sets ( cfg -- )
-    needs-predecessors
-
-    <hashed-dlist> work-list set
-    H{ } clone live-ins set
-    H{ } clone edge-live-ins set
-    H{ } clone live-outs set
-    post-order add-to-work-list
-    work-list get [ liveness-step ] slurp-deque ;
-
-: live-in? ( vreg bb -- ? ) live-in key? ;
-
-: live-out? ( vreg bb -- ? ) live-out key? ;

diff --git a/basis/compiler/cfg/ssa/destruction/destruction.factor b/basis/compiler/cfg/ssa/destruction/destruction.factor
index 197093e5ae47bd834661b4b70203f587b8bbbf4a..981ce423633fe5d2fc8c7da0816a4b8642149c1a 100644 (file)
--- a/basis/compiler/cfg/ssa/destruction/destruction.factor
+++ b/basis/compiler/cfg/ssa/destruction/destruction.factor
@@ -9,7 +9,7 @@ compiler.cfg.def-use
 compiler.cfg.registers
 compiler.cfg.dominance
 compiler.cfg.instructions
-compiler.cfg.liveness.ssa
+compiler.cfg.liveness
 compiler.cfg.ssa.cssa
 compiler.cfg.ssa.interference
 compiler.cfg.ssa.interference.live-ranges
@@ -28,9 +28,9 @@ IN: compiler.cfg.ssa.destruction
 ! 2) Useless ##copy instructions, and all ##phi instructions,
 ! are eliminated, so the register allocator does not have to
 ! remove any redundant operations.
-! 3) A side effect of running this pass is that SSA liveness
-! information is computed, so the register allocator does not
-! need to compute it again.
+! 3) This pass computes live sets and fills out GC maps with
+! compiler.cfg.liveness, so the linear scan register allocator
+! does not need to compute liveness again.
 
 SYMBOL: leader-map
 
@@ -134,7 +134,7 @@ PRIVATE>
     dup construct-cssa
     dup compute-defs
     dup compute-insns
-    dup compute-ssa-live-sets
+    dup compute-live-sets
     dup compute-live-ranges
     dup prepare-coalescing
     process-copies

diff --git a/basis/compiler/cfg/ssa/interference/interference-tests.factor b/basis/compiler/cfg/ssa/interference/interference-tests.factor
index 36c03bc6af192bb540f9c768f3a4209ed8f20141..8648c3ae50abdcab140253cf43b90e2f1715b9e2 100644 (file)
--- a/basis/compiler/cfg/ssa/interference/interference-tests.factor
+++ b/basis/compiler/cfg/ssa/interference/interference-tests.factor
@@ -1,6 +1,6 @@
 USING: accessors compiler.cfg compiler.cfg.debugger
 compiler.cfg.def-use compiler.cfg.dominance
-compiler.cfg.instructions compiler.cfg.liveness.ssa
+compiler.cfg.instructions compiler.cfg.liveness
 compiler.cfg.registers compiler.cfg.predecessors
 compiler.cfg.comparisons compiler.cfg.ssa.interference
 compiler.cfg.ssa.interference.private
@@ -11,7 +11,7 @@ IN: compiler.cfg.ssa.interference.tests
 
 : test-interference ( -- )
     cfg new 0 get >>entry
-    dup compute-ssa-live-sets
+    dup compute-live-sets
     dup compute-defs
     dup compute-insns
     compute-live-ranges ;

diff --git a/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor b/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor
index ffbbf8739f20e40247be5beb27c2b00f725ce130..c3b3d4cf0b8e3f50af06d3480175d3111bc4d4f9 100644 (file)
--- a/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor
+++ b/basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor
@@ -2,7 +2,7 @@
 ! See http://factorcode.org/license.txt for BSD license.
 USING: accessors assocs fry kernel namespaces sequences math
 arrays compiler.cfg.def-use compiler.cfg.instructions
-compiler.cfg.liveness.ssa compiler.cfg.rpo
+compiler.cfg.liveness compiler.cfg.rpo
 compiler.cfg.dominance compiler.cfg ;
 IN: compiler.cfg.ssa.interference.live-ranges