basis/compiler/cfg/ssa/interference/live-ranges/live-ranges.factor

   1 ! Copyright (C) 2009, 2010 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: assocs compiler.cfg compiler.cfg.def-use
   4 compiler.cfg.dominance compiler.cfg.instructions
   5 compiler.cfg.liveness compiler.cfg.rpo kernel math namespaces
   6 sequences ;
   7 IN: compiler.cfg.ssa.interference.live-ranges
   8
   9 ! Live ranges for interference testing
  10
  11 <PRIVATE
  12
  13 SYMBOLS: local-def-indices local-kill-indices ;
  14
  15 : record-defs ( n insn -- )
  16     defs-vregs [ local-def-indices get set-at ] with each ;
  17
  18 : record-uses ( n insn -- )
  19     ! Record live intervals so that all but the first input interfere
  20     ! with the output. This lets us coalesce the output with the
  21     ! first input.
  22     dup uses-vregs [ 2drop ] [
  23         swap def-is-use-insn?
  24         [ [ first local-kill-indices get set-at ] [ rest-slice ] 2bi ] unless
  25         [ 1 + ] dip [ local-kill-indices get set-at ] with each
  26     ] if-empty ;
  27
  28 GENERIC: record-insn ( n insn -- )
  29
  30 M: ##phi record-insn
  31     record-defs ;
  32
  33 M: ##parallel-copy record-insn
  34     [ 2 * ] dip
  35     [ record-defs ]
  36     [ uses-vregs [ local-kill-indices get set-at ] with each ]
  37     2bi ;
  38
  39 M: vreg-insn record-insn
  40     [ 2 * ] dip [ record-defs ] [ record-uses ] 2bi ;
  41
  42 M: insn record-insn
  43     2drop ;
  44
  45 SYMBOLS: def-indices kill-indices ;
  46
  47 : compute-local-live-ranges ( insns -- )
  48     H{ } clone local-def-indices set
  49     H{ } clone local-kill-indices set
  50     [ swap record-insn ] each-index
  51     local-def-indices get basic-block get def-indices get set-at
  52     local-kill-indices get basic-block get kill-indices get set-at ;
  53
  54 PRIVATE>
  55
  56 : compute-live-ranges ( cfg -- )
  57     H{ } clone def-indices set
  58     H{ } clone kill-indices set
  59     [ needs-dominance ]
  60     [ [ compute-local-live-ranges ] simple-analysis ] bi ;
  61
  62 : def-index ( vreg bb -- n )
  63     def-indices get at at ;
  64
  65 ERROR: bad-kill-index vreg bb ;
  66
  67 : kill-index ( vreg bb -- n )
  68     2dup live-out? [ 2drop 1/0. ] [
  69         2dup kill-indices get at at* [ 2nip ] [
  70             drop 2dup live-in?
  71             [ throw-bad-kill-index ] [ 2drop -1/0. ] if
  72         ] if
  73     ] if ;