basis/compiler/cfg/liveness/ssa/ssa.factor

   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 compiler.cfg.utilities
   6 compiler.cfg.predecessors ;
   7 FROM: namespaces => set ;
   8 IN: compiler.cfg.liveness.ssa
   9
  10 ! TODO: merge with compiler.cfg.liveness
  11
  12 ! Assoc mapping basic blocks to sequences of sets of vregs; each sequence
  13 ! is in correspondence with a predecessor
  14 SYMBOL: phi-live-ins
  15
  16 : phi-live-in ( predecessor basic-block -- set ) phi-live-ins get at at ;
  17
  18 SYMBOL: work-list
  19
  20 : add-to-work-list ( basic-blocks -- )
  21     work-list get '[ _ push-front ] each ;
  22
  23 : compute-live-in ( basic-block -- live-in )
  24     [ live-out ] keep instructions>> transfer-liveness ;
  25
  26 : compute-phi-live-in ( basic-block -- phi-live-in )
  27     H{ } clone [
  28         '[ inputs>> [ swap _ conjoin-at ] assoc-each ] each-phi
  29     ] keep ;
  30
  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 ]
  34     bi or ;
  35
  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 ;
  40
  41 : update-live-out ( basic-block -- changed? )
  42     [ compute-live-out ] keep
  43     live-outs get maybe-set-at ;
  44
  45 : liveness-step ( basic-block -- )
  46     dup update-live-out [
  47         dup update-live-in
  48         [ predecessors>> add-to-work-list ] [ drop ] if
  49     ] [ drop ] if ;
  50
  51 : compute-ssa-live-sets ( cfg -- cfg' )
  52     needs-predecessors
  53
  54     <hashed-dlist> work-list set
  55     H{ } clone live-ins set
  56     H{ } clone phi-live-ins set
  57     H{ } clone live-outs set
  58     dup post-order add-to-work-list
  59     work-list get [ liveness-step ] slurp-deque ;
  60
  61 : live-in? ( vreg bb -- ? ) live-in key? ;
  62
  63 : live-out? ( vreg bb -- ? ) live-out key? ;