basis/compiler/cfg/representations/coalescing/coalescing.factor

   1 ! Copyright (C) 2010 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors assocs compiler.cfg.def-use
   4 compiler.cfg.instructions compiler.cfg.rpo disjoint-sets fry
   5 kernel namespaces sequences ;
   6 IN: compiler.cfg.representations.coalescing
   7
   8 ! Find all strongly connected components in the graph where the
   9 ! edges are ##phi or ##copy vreg uses
  10 SYMBOL: components
  11
  12 : init-components ( cfg components -- )
  13     '[
  14         [
  15             defs-vregs [ _ add-atom ] each
  16         ] each
  17     ] simple-analysis ;
  18
  19 GENERIC#: visit-insn 1 ( insn disjoint-set -- )
  20
  21 M: ##copy visit-insn
  22     [ [ dst>> ] [ src>> ] bi ] dip equate ;
  23
  24 M: ##phi visit-insn
  25     [ [ inputs>> values ] [ dst>> ] bi ] dip equate-all-with ;
  26
  27 M: insn visit-insn 2drop ;
  28
  29 : merge-components ( cfg components -- )
  30     '[
  31         [
  32             _ visit-insn
  33         ] each
  34     ] simple-analysis ;
  35
  36 : compute-components ( cfg -- )
  37     <disjoint-set>
  38     [ init-components ]
  39     [ merge-components ]
  40     [ components set drop ] 2tri ;
  41
  42 : vreg>scc ( vreg -- scc )
  43     components get representative ;