compiler.cfg
compiler.cfg.def-use
compiler.cfg.liveness
-compiler.cfg.liveness.ssa
compiler.cfg.registers
compiler.cfg.instructions
compiler.cfg.linearization
-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{
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
! 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 )
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
: 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? ;
+++ /dev/null
-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
+++ /dev/null
-! 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? ;
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
! 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
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
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
: 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 ;
! 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