basis/compiler/cfg/liveness/liveness.factor

   1 ! Copyright (C) 2009 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel accessors assocs sequences sets
   4 compiler.cfg.def-use compiler.cfg.dataflow-analysis
   5 compiler.cfg.instructions ;
   6 IN: compiler.cfg.liveness
   7
   8 ! See http://en.wikipedia.org/wiki/Liveness_analysis
   9 ! Do not run after SSA construction
  10
  11 BACKWARD-ANALYSIS: live
  12
  13 : transfer-liveness ( live-set instructions -- live-set' )
  14     [ clone ] [ <reversed> ] bi* [
  15         [ uses-vregs [ over conjoin ] each ]
  16         [ defs-vregs [ over delete-at ] each ] bi
  17     ] each ;
  18
  19 : local-live-in ( instructions -- live-set )
  20     [ ##phi? not ] filter [ H{ } ] dip transfer-liveness keys ;
  21
  22 M: live-analysis transfer-set
  23     drop instructions>> transfer-liveness ;
  24
  25 M: live-analysis join-sets
  26     drop assoc-combine ;