1 ! Copyright (C) 2009 Slava Pestov.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: accessors arrays assocs fry kernel namespaces
4 sequences sequences.deep
10 compiler.cfg.instructions
11 compiler.cfg.liveness.ssa
13 compiler.cfg.ssa.interference
14 compiler.cfg.ssa.interference.live-ranges
16 IN: compiler.cfg.ssa.destruction
18 ! Maps vregs to leaders.
21 : leader ( vreg -- vreg' ) leader-map get compress-path ;
23 ! Maps leaders to equivalence class elements.
24 SYMBOL: class-element-map
26 : class-elements ( vreg -- elts ) class-element-map get at ;
28 ! Sequence of vreg pairs
31 : init-coalescing ( -- )
32 H{ } clone leader-map set
33 H{ } clone class-element-map set
34 V{ } clone copies set ;
36 : classes-interfere? ( vreg1 vreg2 -- ? )
37 [ leader ] bi@ 2dup eq? [ 2drop f ] [
38 [ class-elements flatten ] bi@ sets-interfere?
41 : update-leaders ( vreg1 vreg2 -- )
42 swap leader-map get set-at ;
44 : merge-classes ( vreg1 vreg2 -- )
45 [ [ class-elements ] bi@ push ]
46 [ drop class-element-map get delete-at ] 2bi ;
48 : eliminate-copy ( vreg1 vreg2 -- )
51 [ update-leaders ] [ merge-classes ] 2bi
54 : introduce-vreg ( vreg -- )
55 [ leader-map get conjoin ]
56 [ [ 1vector ] keep class-element-map get set-at ] bi ;
58 GENERIC: prepare-insn ( insn -- )
60 M: ##copy prepare-insn
61 [ dst>> ] [ src>> ] bi 2array copies get push ;
64 [ dst>> ] [ inputs>> values ] bi
65 [ eliminate-copy ] with each ;
67 M: insn prepare-insn drop ;
69 : prepare-block ( bb -- )
70 instructions>> [ prepare-insn ] each ;
72 : prepare-coalescing ( cfg -- )
74 defs get keys [ introduce-vreg ] each
75 [ prepare-block ] each-basic-block ;
77 : process-copies ( -- )
79 2dup classes-interfere?
80 [ 2drop ] [ eliminate-copy ] if
83 : useless-copy? ( ##copy -- ? )
84 dup ##copy? [ [ dst>> ] [ src>> ] bi eq? ] [ drop f ] if ;
86 : perform-renaming ( cfg -- )
87 leader-map get keys [ dup leader ] H{ } map>assoc renamings set
92 [ [ useless-copy? ] [ ##phi? ] bi or not ] tri
96 : destruct-ssa ( cfg -- cfg' )
100 dup compute-dominance
101 dup compute-live-ranges
102 dup prepare-coalescing
104 dup perform-renaming ;