USING: kernel math namespaces assocs hashtables sequences arrays
accessors vectors combinators sets classes compiler.cfg
compiler.cfg.registers compiler.cfg.instructions
-compiler.cfg.copy-prop compiler.cfg.rpo compiler.cfg.def-use ;
+compiler.cfg.copy-prop compiler.cfg.rpo compiler.cfg.liveness ;
IN: compiler.cfg.alias-analysis
! We try to eliminate redundant slot operations using some simple heuristics.
M: ##set-slot-imm insn-object obj>> resolve ;
M: ##alien-global insn-object drop \ ##alien-global ;
-: inputs ( insns -- seq )
- [ [ ##phi? not ] filter gen-set ] [ kill-set ] bi assoc-diff keys ;
-
: init-alias-analysis ( insns -- insns' )
H{ } clone histories set
H{ } clone vregs>acs set
0 ac-counter set
next-ac heap-ac set
- dup inputs [ set-heap-ac ] each ;
+ dup local-live-in [ set-heap-ac ] each ;
GENERIC: analyze-aliases* ( insn -- insn' )
compiler.cfg
compiler.cfg.rpo
compiler.cfg.def-use
+compiler.cfg.liveness
compiler.cfg.registers
compiler.cfg.instructions
compiler.cfg.linear-scan.mapping
compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
-compiler.cfg.linear-scan.live-intervals
-compiler.cfg.linear-scan.liveness ;
+compiler.cfg.linear-scan.live-intervals ;
IN: compiler.cfg.linear-scan.assignment
! This contains both active and inactive intervals; any interval
cpu.architecture
compiler.cfg
compiler.cfg.rpo
+compiler.cfg.liveness
compiler.cfg.instructions
compiler.cfg.linear-scan.numbering
-compiler.cfg.linear-scan.liveness
compiler.cfg.linear-scan.live-intervals
compiler.cfg.linear-scan.allocation
compiler.cfg.linear-scan.allocation.state
! See http://factorcode.org/license.txt for BSD license.
USING: namespaces kernel assocs accessors sequences math math.order fry
combinators binary-search compiler.cfg.instructions compiler.cfg.registers
-compiler.cfg.def-use compiler.cfg.linear-scan.liveness compiler.cfg.rpo
+compiler.cfg.def-use compiler.cfg.liveness compiler.cfg.rpo
compiler.cfg ;
IN: compiler.cfg.linear-scan.live-intervals
+++ /dev/null
-! Copyright (C) 2009 Slava Pestov.
-! See http://factorcode.org/license.txt for BSD license.
-USING: kernel accessors assocs compiler.cfg.def-use
-compiler.cfg.dataflow-analysis ;
-IN: compiler.cfg.linear-scan.liveness
-
-! See http://en.wikipedia.org/wiki/Liveness_analysis
-
-BACKWARD-ANALYSIS: live
-
-M: live-analysis transfer-set
- drop instructions>>
- [ gen-set assoc-union ] keep
- kill-set assoc-diff ;
-
-M: live-analysis join-sets
- drop assoc-combine ;
\ No newline at end of file
combinators.short-circuit fry kernel locals
make math sequences
compiler.cfg.rpo
+compiler.cfg.liveness
compiler.cfg.utilities
compiler.cfg.instructions
compiler.cfg.linear-scan.assignment
-compiler.cfg.linear-scan.mapping
-compiler.cfg.linear-scan.liveness ;
+compiler.cfg.linear-scan.mapping ;
IN: compiler.cfg.linear-scan.resolve
: add-mapping ( from to reg-class -- )
--- /dev/null
+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 ;
+IN: compiler.cfg.liveness.tests
+
+! Sanity check...
+
+V{
+ T{ ##peek f V int-regs 0 D 0 }
+ T{ ##replace f V int-regs 0 D 0 }
+ T{ ##replace f V int-regs 1 D 1 }
+ T{ ##peek f V int-regs 1 D 1 }
+} 1 test-bb
+
+V{
+ T{ ##replace f V int-regs 2 D 0 }
+} 2 test-bb
+
+V{
+ T{ ##replace f V int-regs 3 D 0 }
+} 3 test-bb
+
+1 get 2 get 3 get V{ } 2sequence >>successors drop
+
+cfg new 1 get >>entry
+compute-predecessors
+compute-live-sets
+
+[
+ H{
+ { V int-regs 1 V int-regs 1 }
+ { V int-regs 2 V int-regs 2 }
+ { V int-regs 3 V int-regs 3 }
+ }
+]
+[ 1 get live-in ]
+unit-test
\ No newline at end of file
--- /dev/null
+! Copyright (C) 2009 Slava Pestov.
+! See http://factorcode.org/license.txt for BSD license.
+USING: kernel accessors assocs sequences sets
+compiler.cfg.def-use compiler.cfg.dataflow-analysis
+compiler.cfg.instructions ;
+IN: compiler.cfg.liveness
+
+! See http://en.wikipedia.org/wiki/Liveness_analysis
+! Do not run after SSA construction
+
+BACKWARD-ANALYSIS: live
+
+: transfer-liveness ( live-set instructions -- live-set' )
+ [ clone ] [ <reversed> ] bi* [
+ [ uses-vregs [ over conjoin ] each ]
+ [ defs-vregs [ over delete-at ] each ] bi
+ ] each ;
+
+: local-live-in ( instructions -- live-set )
+ [ ##phi? not ] filter [ H{ } ] dip transfer-liveness keys ;
+
+M: live-analysis transfer-set
+ drop instructions>> transfer-liveness ;
+
+M: live-analysis join-sets
+ drop assoc-combine ;
\ No newline at end of file