1 ! Copyright (C) 2009 Slava Pestov.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel namespaces deques accessors sets sequences assocs fry
4 hashtables dlists compiler.cfg.def-use compiler.cfg.instructions
5 compiler.cfg.rpo compiler.cfg.liveness ;
6 IN: compiler.cfg.liveness.ssa
8 ! TODO: merge with compiler.cfg.liveness
10 ! Assoc mapping basic blocks to sequences of sets of vregs; each sequence
11 ! is in conrrespondence with a predecessor
14 : phi-live-in ( predecessor basic-block -- set ) phi-live-ins get at at ;
18 : add-to-work-list ( basic-blocks -- )
19 work-list get '[ _ push-front ] each ;
21 : compute-live-in ( basic-block -- live-in )
22 [ live-out ] keep instructions>> transfer-liveness ;
24 : compute-phi-live-in ( basic-block -- phi-live-in )
25 instructions>> [ ##phi? ] filter [ f ] [
27 '[ inputs>> [ swap _ conjoin-at ] assoc-each ] each
31 : update-live-in ( basic-block -- changed? )
32 [ [ compute-live-in ] keep live-ins get maybe-set-at ]
33 [ [ compute-phi-live-in ] keep phi-live-ins get maybe-set-at ]
36 : compute-live-out ( basic-block -- live-out )
37 [ successors>> [ live-in ] map ]
38 [ dup successors>> [ phi-live-in ] with map ] bi
39 append assoc-combine ;
41 : update-live-out ( basic-block -- changed? )
42 [ compute-live-out ] keep
43 live-outs get maybe-set-at ;
45 : liveness-step ( basic-block -- )
48 [ predecessors>> add-to-work-list ] [ drop ] if
51 : compute-ssa-live-sets ( cfg -- cfg' )
52 <hashed-dlist> work-list set
53 H{ } clone live-ins set
54 H{ } clone phi-live-ins set
55 H{ } clone live-outs set
56 dup post-order add-to-work-list
57 work-list get [ liveness-step ] slurp-deque ;