basis/compiler/cfg/ssa/destruction/destruction.factor

   1 ! Copyright (C) 2009 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors assocs fry kernel locals math math.order
   4 sequences namespaces sets
   5 compiler.cfg.rpo
   6 compiler.cfg.def-use
   7 compiler.cfg.utilities
   8 compiler.cfg.dominance
   9 compiler.cfg.instructions
  10 compiler.cfg.liveness.ssa
  11 compiler.cfg.critical-edges
  12 compiler.cfg.ssa.destruction.state
  13 compiler.cfg.ssa.destruction.forest
  14 compiler.cfg.ssa.destruction.copies
  15 compiler.cfg.ssa.destruction.renaming
  16 compiler.cfg.ssa.destruction.live-ranges
  17 compiler.cfg.ssa.destruction.process-blocks ;
  18 IN: compiler.cfg.ssa.destruction
  19
  20 ! Based on "Fast Copy Coalescing and Live-Range Identification"
  21 ! http://www.cs.ucsd.edu/classes/sp02/cse231/kenpldi.pdf
  22
  23 ! Dominance, liveness and def-use need to be computed
  24
  25 : process-blocks ( cfg -- )
  26     [ [ process-block ] if-has-phis ] each-basic-block ;
  27
  28 SYMBOL: seen
  29
  30 :: visit-renaming ( dst assoc src bb -- )
  31     src seen get key? [
  32         src dst bb add-waiting
  33         src assoc delete-at
  34     ] [ src seen get conjoin ] if ;
  35
  36 :: break-interferences ( -- )
  37     H{ } clone seen set
  38     renaming-sets get [| dst assoc |
  39         assoc [| src bb |
  40             dst assoc src bb visit-renaming
  41         ] assoc-each
  42     ] assoc-each ;
  43
  44 : remove-phis-from-block ( bb -- )
  45     instructions>> [ ##phi? not ] filter-here ;
  46
  47 : remove-phis ( cfg -- )
  48     [ [ remove-phis-from-block ] if-has-phis ] each-basic-block ;
  49
  50 : destruct-ssa ( cfg -- cfg' )
  51     dup cfg-has-phis? [
  52         dup split-critical-edges
  53         compute-ssa-live-sets
  54         init-coalescing
  55         dup compute-def-use
  56         dup compute-dominance
  57         dup compute-live-ranges
  58         dup process-blocks
  59         break-interferences
  60         dup perform-renaming
  61         insert-copies
  62         dup remove-phis
  63     ] when ;