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.liveness compiler.cfg.local ;
+compiler.cfg.copy-prop compiler.cfg.rpo compiler.cfg.def-use ;
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 ;
-: init-alias-analysis ( live-in -- )
+: 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
H{ } clone acs>vregs set
0 ac-counter set
next-ac heap-ac set
- [ set-heap-ac ] each ;
+ dup inputs [ set-heap-ac ] each ;
GENERIC: analyze-aliases* ( insn -- insn' )
[ insn# set eliminate-dead-stores* ] map-index sift ;
: alias-analysis-step ( insns -- insns' )
+ init-alias-analysis
analyze-aliases
compute-live-stores
eliminate-dead-stores ;
: alias-analysis ( cfg -- cfg' )
- [ init-alias-analysis ] [ alias-analysis-step ] local-optimization ;
\ No newline at end of file
+ [ alias-analysis-step ] local-optimization ;
\ No newline at end of file
! Copyright (C) 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel compiler.cfg.instructions compiler.cfg.rpo
-compiler.cfg.def-use compiler.cfg.linearization compiler.cfg.liveness
+compiler.cfg.def-use compiler.cfg.linearization
combinators.short-circuit accessors math sequences sets assocs ;
IN: compiler.cfg.checker
2dup subset? [ 2drop ] [ undefined-values ] if ;
: check-cfg ( cfg -- )
- compute-liveness
- [ entry>> live-in assoc-empty? [ bad-live-in ] unless ]
[ [ check-basic-block ] each-basic-block ]
[ flatten-cfg check-mr ]
- tri ;
+ bi ;
GENERIC# compute-in-set 2 ( bb out-sets dfa -- set )
-M: kill-block compute-in-set 3drop f ;
+! M: kill-block compute-in-set 3drop f ;
M:: basic-block compute-in-set ( bb out-sets dfa -- set )
bb dfa predecessors [ out-sets at ] map dfa join-sets ;
GENERIC# compute-out-set 2 ( bb out-sets dfa -- set )
-M: kill-block compute-out-set 3drop f ;
+! M: kill-block compute-out-set 3drop f ;
M:: basic-block compute-out-set ( bb in-sets dfa -- set )
bb in-sets at bb dfa transfer-set ;
compiler.cfg.builder compiler.cfg.linearization
compiler.cfg.registers compiler.cfg.stack-frame
compiler.cfg.linear-scan compiler.cfg.two-operand
-compiler.cfg.liveness compiler.cfg.optimizer
+compiler.cfg.optimizer
compiler.cfg.mr compiler.cfg ;
IN: compiler.cfg.debugger
! Copyright (C) 2008, 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays kernel assocs compiler.cfg.instructions ;
+USING: accessors arrays kernel assocs sequences
+sets compiler.cfg.instructions ;
IN: compiler.cfg.def-use
GENERIC: defs-vregs ( insn -- seq )
_conditional-branch
_compare-imm-branch
_dispatch ;
+
+: map-unique ( seq quot -- assoc )
+ map concat unique ; inline
+
+: gen-set ( instructions -- seq )
+ [ uses-vregs ] map-unique ;
+
+: kill-set ( instructions -- seq )
+ [ defs-vregs ] map-unique ;
fry make combinators sets locals
cpu.architecture
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.live-intervals
+compiler.cfg.linear-scan.liveness ;
IN: compiler.cfg.linear-scan.assignment
! This contains both active and inactive intervals; any interval
] V{ } make
] change-instructions drop ;
-: assign-registers ( live-intervals rpo -- )
+: assign-registers ( live-intervals cfg -- )
[ init-assignment ] dip
- [ assign-registers-in-block ] each ;
+ [ assign-registers-in-block ] each-basic-block ;
compiler.cfg.optimizer
compiler.cfg.instructions
compiler.cfg.registers
-compiler.cfg.liveness
compiler.cfg.predecessors
compiler.cfg.rpo
compiler.cfg.linearization
[
cfg new 0 get >>entry
compute-predecessors
- compute-liveness
- dup reverse-post-order
- { { int-regs regs } } (linear-scan)
+ dup { { int-regs regs } } (linear-scan)
cfg-changed
flatten-cfg 1array mr.
] with-scope ;
! early in bootstrap on x86-32
[ t ] [
[
- H{ } clone live-ins set
- H{ } clone live-outs set
- H{ } clone phi-live-ins set
T{ basic-block
{ id 12345 }
{ instructions
T{ ##replace f V int-regs 5 D 0 }
}
}
- } dup 1array { { int-regs V{ 0 1 2 3 } } } (linear-scan)
+ } cfg new over >>entry
+ { { int-regs V{ 0 1 2 3 } } } (linear-scan)
instructions>> first
live-values>> assoc-empty?
] with-scope
compiler.cfg.rpo
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
! by Omri Traub, Glenn Holloway, Michael D. Smith
! http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.8435
-:: (linear-scan) ( rpo machine-registers -- )
- rpo number-instructions
- rpo compute-live-intervals machine-registers allocate-registers
- rpo assign-registers
- rpo resolve-data-flow
- rpo check-numbering ;
+:: (linear-scan) ( cfg machine-registers -- )
+ cfg compute-live-sets
+ cfg number-instructions
+ cfg compute-live-intervals machine-registers allocate-registers
+ cfg assign-registers
+ cfg resolve-data-flow
+ cfg check-numbering ;
: linear-scan ( cfg -- cfg' )
[
init-mapping
- dup reverse-post-order machine-registers (linear-scan)
+ dup machine-registers (linear-scan)
spill-counts get >>spill-counts
cfg-changed
] with-scope ;
! 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.liveness compiler.cfg ;
+compiler.cfg.def-use compiler.cfg.linear-scan.liveness compiler.cfg.rpo
+compiler.cfg ;
IN: compiler.cfg.linear-scan.live-intervals
TUPLE: live-range from to ;
} cleave
] each ;
-: compute-live-intervals ( rpo -- live-intervals )
+: compute-live-intervals ( cfg -- live-intervals )
H{ } clone [
live-intervals set
- <reversed> [ compute-live-intervals-step ] each
+ post-order [ compute-live-intervals-step ] each
] keep values dup finish-live-intervals ;
: relevant-ranges ( interval1 interval2 -- ranges1 ranges2 )
--- /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
! Copyright (C) 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: kernel accessors math sequences grouping namespaces ;
+USING: kernel accessors math sequences grouping namespaces
+compiler.cfg.rpo ;
IN: compiler.cfg.linear-scan.numbering
: number-instructions ( rpo -- )
instructions>> [
[ (>>insn#) ] [ drop 2 + ] 2bi
] each
- ] each drop ;
+ ] each-basic-block drop ;
SYMBOL: check-numbering?
dup instructions>> [ insn#>> ] map sift [ <= ] monotonic?
[ drop ] [ bad-numbering ] if ;
-: check-numbering ( rpo -- )
- check-numbering? get [ [ check-block-numbering ] each ] [ drop ] if ;
\ No newline at end of file
+: check-numbering ( cfg -- )
+ check-numbering? get [ [ check-block-numbering ] each-basic-block ] [ drop ] if ;
\ No newline at end of file
USING: accessors arrays assocs combinators
combinators.short-circuit fry kernel locals
make math sequences
+compiler.cfg.rpo
compiler.cfg.utilities
compiler.cfg.instructions
compiler.cfg.linear-scan.assignment
-compiler.cfg.linear-scan.mapping compiler.cfg.liveness ;
+compiler.cfg.linear-scan.mapping
+compiler.cfg.linear-scan.liveness ;
IN: compiler.cfg.linear-scan.resolve
: add-mapping ( from to reg-class -- )
: resolve-block-data-flow ( bb -- )
dup successors>> [ resolve-edge-data-flow ] with each ;
-: resolve-data-flow ( rpo -- )
- [ resolve-block-data-flow ] each ;
+: resolve-data-flow ( cfg -- )
+ [ resolve-block-data-flow ] each-basic-block ;
combinators assocs arrays locals cpu.architecture
compiler.cfg
compiler.cfg.rpo
-compiler.cfg.liveness
compiler.cfg.comparisons
compiler.cfg.stack-frame
compiler.cfg.instructions ;
+++ /dev/null
-Slava Pestov
\ No newline at end of file
+++ /dev/null
-USING: compiler.cfg compiler.cfg.instructions compiler.cfg.registers
-compiler.cfg.liveness accessors tools.test cpu.architecture ;
-IN: compiler.cfg.liveness.tests
-
-[
- H{
- { "A" H{ { V int-regs 1 V int-regs 1 } { V int-regs 4 V int-regs 4 } } }
- { "B" H{ { V int-regs 3 V int-regs 3 } { V int-regs 2 V int-regs 2 } } }
- }
-] [
- <basic-block> V{
- T{ ##phi f V int-regs 0 { { "A" V int-regs 1 } { "B" V int-regs 2 } } }
- T{ ##phi f V int-regs 1 { { "B" V int-regs 3 } { "A" V int-regs 4 } } }
- } >>instructions compute-phi-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 namespaces deques accessors sets sequences assocs fry
-hashtables dlists compiler.cfg.def-use compiler.cfg.instructions
-compiler.cfg.rpo ;
-IN: compiler.cfg.liveness
-
-! This is a backward dataflow analysis. See http://en.wikipedia.org/wiki/Liveness_analysis
-
-! Assoc mapping basic blocks to sets of vregs
-SYMBOL: live-ins
-
-: live-in ( basic-block -- set ) live-ins get at ;
-
-! Assoc mapping basic blocks to sequences of sets of vregs; each sequence
-! is in conrrespondence with a predecessor
-SYMBOL: phi-live-ins
-
-: phi-live-in ( predecessor basic-block -- set ) phi-live-ins get at at ;
-
-! Assoc mapping basic blocks to sets of vregs
-SYMBOL: live-outs
-
-: live-out ( basic-block -- set ) live-outs get at ;
-
-SYMBOL: work-list
-
-: add-to-work-list ( basic-blocks -- )
- work-list get '[ _ push-front ] each ;
-
-: map-unique ( seq quot -- assoc )
- map concat unique ; inline
-
-: gen-set ( instructions -- seq )
- [ ##phi? not ] filter [ uses-vregs ] map-unique ;
-
-: kill-set ( instructions -- seq )
- [ [ defs-vregs ] [ temp-vregs ] bi append ] map-unique ;
-
-: compute-live-in ( basic-block -- live-in )
- dup instructions>>
- [ [ live-out ] [ gen-set ] bi* assoc-union ]
- [ nip kill-set ]
- 2bi assoc-diff ;
-
-: compute-phi-live-in ( basic-block -- phi-live-in )
- instructions>> [ ##phi? ] filter [ f ] [
- H{ } clone [
- '[ inputs>> [ swap _ conjoin-at ] assoc-each ] each
- ] keep
- ] if-empty ;
-
-: update-live-in ( basic-block -- changed? )
- [ [ compute-live-in ] keep live-ins get maybe-set-at ]
- [ [ compute-phi-live-in ] keep phi-live-ins get maybe-set-at ]
- bi and ;
-
-: compute-live-out ( basic-block -- live-out )
- [ successors>> [ live-in ] map ]
- [ dup successors>> [ phi-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-liveness ( cfg -- cfg' )
- <hashed-dlist> work-list set
- H{ } clone live-ins set
- H{ } clone phi-live-ins set
- H{ } clone live-outs set
- dup post-order add-to-work-list
- work-list get [ liveness-step ] slurp-deque ;
+++ /dev/null
-Slava Pestov
\ No newline at end of file
+++ /dev/null
-! Copyright (C) 2009 Slava Pestov.
-! See http://factorcode.org/license.txt for BSD license.
-USING: locals accessors kernel assocs namespaces
-compiler.cfg compiler.cfg.liveness compiler.cfg.rpo ;
-IN: compiler.cfg.local
-
-:: optimize-basic-block ( bb init-quot insn-quot -- )
- bb basic-block set
- bb live-in keys init-quot call
- bb insn-quot change-instructions drop ; inline
-
-:: local-optimization ( cfg init-quot: ( live-in -- ) insn-quot: ( insns -- insns' ) -- cfg' )
- cfg [ init-quot insn-quot optimize-basic-block ] each-basic-block
- cfg ; inline
\ No newline at end of file
! Copyright (C) 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: compiler.cfg.linearization compiler.cfg.two-operand
-compiler.cfg.liveness compiler.cfg.gc-checks compiler.cfg.linear-scan
+compiler.cfg.gc-checks compiler.cfg.linear-scan
compiler.cfg.build-stack-frame compiler.cfg.rpo ;
IN: compiler.cfg.mr
: build-mr ( cfg -- mr )
convert-two-operand
- compute-liveness
insert-gc-checks
linear-scan
flatten-cfg
compiler.cfg.value-numbering
compiler.cfg.dce
compiler.cfg.write-barrier
-compiler.cfg.liveness
compiler.cfg.rpo
compiler.cfg.phi-elimination
compiler.cfg.checker ;
join-blocks
compute-predecessors
stack-analysis
- compute-liveness
alias-analysis
value-numbering
compute-predecessors
SYMBOL: renamings
-: rename-value ( vreg -- vreg' ) renamings get at ;
+: rename-value ( vreg -- vreg' ) renamings get ?at drop ;
GENERIC: rename-insn-defs ( insn -- )
: each-basic-block ( cfg quot -- )
[ reverse-post-order ] dip each ; inline
+
+: optimize-basic-block ( bb quot -- )
+ [ drop basic-block set ]
+ [ change-instructions drop ] 2bi ; inline
+
+: local-optimization ( cfg quot: ( insns -- insns' ) -- cfg' )
+ dupd '[ _ optimize-basic-block ] each-basic-block ; inline
\ No newline at end of file
! Copyright (C) 2008, 2009 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
USING: accessors kernel sequences make compiler.cfg.instructions
-compiler.cfg.local cpu.architecture ;
+compiler.cfg.rpo cpu.architecture ;
IN: compiler.cfg.two-operand
! On x86, instructions take the form x = x op y
: convert-two-operand ( cfg -- cfg' )
two-operand? [
- [ drop ]
[ [ [ convert-two-operand* ] each ] V{ } make ]
local-optimization
] when ;
IN: compiler.cfg.value-numbering.expressions
! Referentially-transparent expressions
-TUPLE: expr op ;
TUPLE: unary-expr < expr in ;
TUPLE: binary-expr < expr in1 in2 ;
TUPLE: commutative-expr < binary-expr ;
} cond
] [ 2drop f ] if ;
-! Expressions whose values are inputs to the basic block. We
-! can eliminate a second computation having the same 'n' as
-! the first one; we can also eliminate input-exprs whose
-! result is not used.
-TUPLE: input-expr < expr n ;
-
-SYMBOL: input-expr-counter
-
-: next-input-expr ( class -- expr )
- input-expr-counter [ dup 1 + ] change input-expr boa ;
-
: constant>vn ( constant -- vn ) <constant> expr>vn ; inline
GENERIC: >expr ( insn -- expr )
M: ##compare-float >expr compare>expr ;
-M: ##flushable >expr class next-input-expr ;
+M: ##flushable >expr drop next-input-expr ;
: init-expressions ( -- )
0 input-expr-counter set ;
! biassoc mapping expressions to value numbers
SYMBOL: exprs>vns
+TUPLE: expr op ;
+
: expr>vn ( expr -- vn ) exprs>vns get [ drop next-vn ] cache ;
: vn>expr ( vn -- expr ) exprs>vns get value-at ;
+! Expressions whose values are inputs to the basic block.
+TUPLE: input-expr < expr n ;
+
+SYMBOL: input-expr-counter
+
+: next-input-expr ( -- expr )
+ f input-expr-counter counter input-expr boa ;
+
SYMBOL: vregs>vns
-: vreg>vn ( vreg -- vn ) vregs>vns get at ;
+: vreg>vn ( vreg -- vn )
+ vregs>vns get [ drop next-input-expr expr>vn ] cache ;
: vn>vreg ( vn -- vreg ) vregs>vns get value-at ;
compiler.cfg.registers compiler.cfg.debugger compiler.cfg.comparisons
cpu.architecture tools.test kernel math combinators.short-circuit
accessors sequences compiler.cfg.predecessors locals
-compiler.cfg.phi-elimination compiler.cfg.dce compiler.cfg.liveness
+compiler.cfg.phi-elimination compiler.cfg.dce
compiler.cfg assocs vectors arrays layouts namespaces ;
: trim-temps ( insns -- insns )
} 1|| [ f >>temp ] when
] map ;
-: test-value-numbering ( insns -- insns )
- { } init-value-numbering
- value-numbering-step ;
-
! Folding constants together
[
{
T{ ##load-reference f V int-regs 1 -0.0 }
T{ ##replace f V int-regs 0 D 0 }
T{ ##replace f V int-regs 1 D 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-reference f V int-regs 1 0.0 }
T{ ##replace f V int-regs 0 D 0 }
T{ ##replace f V int-regs 1 D 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-reference f V int-regs 1 t }
T{ ##replace f V int-regs 0 D 0 }
T{ ##replace f V int-regs 1 D 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
! Copy propagation
T{ ##peek f V int-regs 45 D 1 }
T{ ##copy f V int-regs 48 V int-regs 45 }
T{ ##compare-imm-branch f V int-regs 48 7 cc/= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
! Compare propagation
T{ ##compare f V int-regs 4 V int-regs 2 V int-regs 1 cc> }
T{ ##compare-imm f V int-regs 6 V int-regs 4 5 cc/= }
T{ ##replace f V int-regs 6 D 0 }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
[
T{ ##compare f V int-regs 4 V int-regs 2 V int-regs 1 cc<= }
T{ ##compare-imm f V int-regs 6 V int-regs 4 5 cc= }
T{ ##replace f V int-regs 6 D 0 }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
[
T{ ##compare-float f V int-regs 12 V double-float-regs 10 V double-float-regs 11 cc< }
T{ ##compare-imm f V int-regs 14 V int-regs 12 5 cc= }
T{ ##replace f V int-regs 14 D 0 }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
[
T{ ##peek f V int-regs 30 D -2 }
T{ ##compare f V int-regs 33 V int-regs 29 V int-regs 30 cc<= }
T{ ##compare-imm-branch f V int-regs 33 5 cc/= }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
! Immediate operand conversion
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##add f V int-regs 2 V int-regs 0 V int-regs 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##add f V int-regs 2 V int-regs 1 V int-regs 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##sub f V int-regs 2 V int-regs 0 V int-regs 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##sub f V int-regs 1 V int-regs 0 V int-regs 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##mul f V int-regs 2 V int-regs 0 V int-regs 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##mul f V int-regs 2 V int-regs 1 V int-regs 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 1 D 0 }
T{ ##mul-imm f V int-regs 2 V int-regs 1 8 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##and f V int-regs 2 V int-regs 0 V int-regs 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##and f V int-regs 2 V int-regs 1 V int-regs 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##or f V int-regs 2 V int-regs 0 V int-regs 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##or f V int-regs 2 V int-regs 1 V int-regs 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##xor f V int-regs 2 V int-regs 0 V int-regs 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##xor f V int-regs 2 V int-regs 1 V int-regs 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##compare f V int-regs 2 V int-regs 0 V int-regs 1 cc<= }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##compare f V int-regs 2 V int-regs 1 V int-regs 0 cc<= }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##compare-branch f V int-regs 0 V int-regs 1 cc<= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 100 }
T{ ##compare-branch f V int-regs 1 V int-regs 0 cc<= }
- } test-value-numbering trim-temps
+ } value-numbering-step trim-temps
] unit-test
! Reassociation
T{ ##add f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##add f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##add f V int-regs 2 V int-regs 1 V int-regs 0 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##add f V int-regs 4 V int-regs 3 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##add f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##sub f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##sub f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##sub f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##mul f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##mul f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##mul f V int-regs 2 V int-regs 1 V int-regs 0 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##mul f V int-regs 4 V int-regs 3 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##and f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##and f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##and f V int-regs 2 V int-regs 1 V int-regs 0 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##and f V int-regs 4 V int-regs 3 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##or f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##or f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##or f V int-regs 2 V int-regs 1 V int-regs 0 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##or f V int-regs 4 V int-regs 3 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##xor f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##xor f V int-regs 4 V int-regs 2 V int-regs 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##xor f V int-regs 2 V int-regs 1 V int-regs 0 }
T{ ##load-immediate f V int-regs 3 50 }
T{ ##xor f V int-regs 4 V int-regs 3 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
! Simplification
T{ ##sub f V int-regs 2 V int-regs 1 V int-regs 1 }
T{ ##add f V int-regs 3 V int-regs 0 V int-regs 2 }
T{ ##replace f V int-regs 3 D 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##sub f V int-regs 2 V int-regs 1 V int-regs 1 }
T{ ##sub f V int-regs 3 V int-regs 0 V int-regs 2 }
T{ ##replace f V int-regs 3 D 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##sub f V int-regs 2 V int-regs 1 V int-regs 1 }
T{ ##or f V int-regs 3 V int-regs 0 V int-regs 2 }
T{ ##replace f V int-regs 3 D 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##sub f V int-regs 2 V int-regs 1 V int-regs 1 }
T{ ##xor f V int-regs 3 V int-regs 0 V int-regs 2 }
T{ ##replace f V int-regs 3 D 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 1 }
T{ ##mul f V int-regs 2 V int-regs 0 V int-regs 1 }
T{ ##replace f V int-regs 2 D 0 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
! Constant folding
T{ ##load-immediate f V int-regs 1 1 }
T{ ##load-immediate f V int-regs 2 3 }
T{ ##add f V int-regs 3 V int-regs 1 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 1 }
T{ ##load-immediate f V int-regs 2 3 }
T{ ##sub f V int-regs 3 V int-regs 1 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 2 }
T{ ##load-immediate f V int-regs 2 3 }
T{ ##mul f V int-regs 3 V int-regs 1 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 2 }
T{ ##load-immediate f V int-regs 2 1 }
T{ ##and f V int-regs 3 V int-regs 1 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 2 }
T{ ##load-immediate f V int-regs 2 1 }
T{ ##or f V int-regs 3 V int-regs 1 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 2 }
T{ ##load-immediate f V int-regs 2 3 }
T{ ##xor f V int-regs 3 V int-regs 1 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 1 }
T{ ##shl-imm f V int-regs 3 V int-regs 1 3 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
cell 8 = [
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 -1 }
T{ ##shr-imm f V int-regs 3 V int-regs 1 16 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
] when
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 1 -8 }
T{ ##sar-imm f V int-regs 3 V int-regs 1 1 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
cell 8 = [
T{ ##load-immediate f V int-regs 1 65536 }
T{ ##shl-imm f V int-regs 2 V int-regs 1 31 }
T{ ##add f V int-regs 3 V int-regs 0 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##peek f V int-regs 0 D 0 }
T{ ##load-immediate f V int-regs 2 140737488355328 }
T{ ##add f V int-regs 3 V int-regs 0 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 2 2147483647 }
T{ ##add f V int-regs 3 V int-regs 0 V int-regs 2 }
T{ ##add f V int-regs 4 V int-regs 3 V int-regs 2 }
- } test-value-numbering
+ } value-numbering-step
] unit-test
] when
T{ ##load-immediate f V int-regs 1 1 }
T{ ##load-immediate f V int-regs 2 2 }
T{ ##compare f V int-regs 3 V int-regs 1 V int-regs 2 cc= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 1 }
T{ ##load-immediate f V int-regs 2 2 }
T{ ##compare f V int-regs 3 V int-regs 1 V int-regs 2 cc/= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 1 }
T{ ##load-immediate f V int-regs 2 2 }
T{ ##compare f V int-regs 3 V int-regs 1 V int-regs 2 cc< }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
T{ ##load-immediate f V int-regs 1 1 }
T{ ##load-immediate f V int-regs 2 2 }
T{ ##compare f V int-regs 3 V int-regs 2 V int-regs 1 cc< }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##compare f V int-regs 1 V int-regs 0 V int-regs 0 cc< }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##compare f V int-regs 1 V int-regs 0 V int-regs 0 cc<= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##compare f V int-regs 1 V int-regs 0 V int-regs 0 cc> }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##compare f V int-regs 1 V int-regs 0 V int-regs 0 cc>= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##compare f V int-regs 1 V int-regs 0 V int-regs 0 cc/= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
[
{
T{ ##peek f V int-regs 0 D 0 }
T{ ##compare f V int-regs 1 V int-regs 0 V int-regs 0 cc= }
- } test-value-numbering
+ } value-numbering-step
] unit-test
: test-branch-folding ( insns -- insns' n )
<basic-block>
- [ V{ 0 1 } clone >>successors basic-block set test-value-numbering ] keep
+ [ V{ 0 1 } clone >>successors basic-block set value-numbering-step ] keep
successors>> first ;
[
[ ] [
cfg new 0 get >>entry
- compute-liveness
value-numbering
compute-predecessors
eliminate-phis drop
[ ] [
cfg new 0 get >>entry
compute-predecessors
- compute-liveness
value-numbering
compute-predecessors
eliminate-dead-code
[ ] [
cfg new 0 get >>entry
- compute-liveness value-numbering eliminate-dead-code drop
+ value-numbering eliminate-dead-code drop
] unit-test
[ f ] [ 1 get instructions>> [ ##peek? ] any? ] unit-test
USING: namespaces assocs biassocs classes kernel math accessors
sorting sets sequences fry
compiler.cfg
-compiler.cfg.local
-compiler.cfg.liveness
+compiler.cfg.rpo
compiler.cfg.renaming
compiler.cfg.value-numbering.graph
compiler.cfg.value-numbering.expressions
IN: compiler.cfg.value-numbering
! Local value numbering. Predecessors must be recomputed after this
-
-: number-input-values ( live-in -- )
- [ [ f next-input-expr simplify ] dip set-vn ] each ;
-
-: init-value-numbering ( live-in -- )
- init-value-graph
- init-expressions
- number-input-values ;
-
: vreg>vreg-mapping ( -- assoc )
vregs>vns get [ keys ] keep
'[ dup _ [ at ] [ value-at ] bi ] H{ } map>assoc ;
] with-variable ;
: value-numbering-step ( insns -- insns' )
- [ rewrite ] map dup rename-uses ;
+ init-value-graph
+ init-expressions
+ [ rewrite ] map
+ dup rename-uses ;
: value-numbering ( cfg -- cfg' )
- [ init-value-numbering ] [ value-numbering-step ] local-optimization
- cfg-changed ;
+ [ value-numbering-step ] local-optimization cfg-changed ;
! See http://factorcode.org/license.txt for BSD license.
USING: kernel accessors namespaces assocs sets sequences locals
compiler.cfg compiler.cfg.instructions compiler.cfg.copy-prop
-compiler.cfg.liveness compiler.cfg.local ;
+compiler.cfg.rpo ;
IN: compiler.cfg.write-barrier
! Eliminate redundant write barrier hits.
[ eliminate-write-barrier ] map sift ;
: eliminate-write-barriers ( cfg -- cfg' )
- [ drop ] [ write-barriers-step ] local-optimization ;
+ [ write-barriers-step ] local-optimization ;