basis/compiler/cfg/copy-prop/copy-prop.factor

   1 ! Copyright (C) 2008, 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.predecessors
   5 compiler.cfg.renaming compiler.cfg.rpo compiler.cfg.utilities
   6 fry grouping kernel namespaces sequences ;
   7 FROM: namespaces => set ;
   8 IN: compiler.cfg.copy-prop
   9
  10 <PRIVATE
  11
  12 SYMBOL: changed?
  13
  14 SYMBOL: copies
  15
  16 ! Initialized per-basic-block; a mapping from inputs to dst for
  17 ! eliminating redundant ##phi instructions
  18 SYMBOL: phis
  19
  20 : resolve ( vreg -- vreg )
  21     copies get at ;
  22
  23 : (record-copy) ( dst src copies -- )
  24     swapd maybe-set-at [ changed? on ] when ; inline
  25
  26 : record-copy ( dst src -- )
  27     copies get (record-copy) ; inline
  28
  29 : record-copies ( seq -- )
  30     copies get '[ dup _ (record-copy) ] each ; inline
  31
  32 GENERIC: visit-insn ( insn -- )
  33
  34 M: ##copy visit-insn
  35     [ dst>> ] [ src>> resolve ] bi
  36     [ record-copy ] [ drop ] if* ;
  37
  38 : useless-phi ( dst inputs -- ) first record-copy ;
  39
  40 : redundant-phi ( dst inputs -- ) phis get at record-copy ;
  41
  42 : record-phi ( dst inputs -- )
  43     [ phis get set-at ] [ drop dup record-copy ] 2bi ;
  44
  45 M: ##phi visit-insn
  46     [ dst>> ] [ inputs>> values [ resolve ] map ] bi
  47     dup phis get key? [ redundant-phi ] [
  48         dup sift
  49         dup all-equal?
  50         [ nip useless-phi ]
  51         [ drop record-phi ] if
  52     ] if ;
  53
  54 M: vreg-insn visit-insn
  55     defs-vregs record-copies  ;
  56
  57 M: insn visit-insn drop ;
  58
  59 : (collect-copies) ( cfg -- )
  60     [
  61         phis get clear-assoc
  62         [ visit-insn ] each
  63     ] simple-analysis ;
  64
  65 : collect-copies ( cfg -- )
  66     H{ } clone copies set
  67     H{ } clone phis set
  68     '[
  69         changed? off
  70         _ (collect-copies)
  71         changed? get
  72     ] loop ;
  73
  74 GENERIC: update-insn ( insn -- keep? )
  75
  76 M: ##copy update-insn drop f ;
  77
  78 M: ##phi update-insn
  79     dup call-next-method drop
  80     [ dst>> ] [ inputs>> values ] bi [ = not ] with any? ;
  81
  82 M: vreg-insn update-insn rename-insn-uses t ;
  83
  84 M: insn update-insn drop t ;
  85
  86 : rename-copies ( cfg -- )
  87     copies get renamings set
  88     [ [ update-insn ] filter! ] simple-optimization ;
  89
  90 PRIVATE>
  91
  92 ! Certain parts of the GVN pass may come together here and
  93 ! sabotage the correctness of the CFG:
  94 !
  95 !   1) compiler.cfg.gvn.comparisons:fold-branch may remove some
  96 !   predecessors of a block (hence predecessors-changed at the
  97 !   end of compiler.cfg.gvn:value-numbering).
  98 !
  99 !   2) At the moment in compiler.cfg.gvn:value-numbering,
 100 !   ##phis with equivalent inputs (i.e., identical value
 101 !   numbers) will be converted into ##copy insns; thus, some
 102 !   ##copies may show up *before* ##phis within a basic block,
 103 !   even though ##phis should come at the very beginning of a
 104 !   block.
 105 !
 106 ! Thus, the call to needs-predecessors in copy-propagation may
 107 ! wind up failing to prune dead inputs to particular ##phis in
 108 ! a block (if they're preceded by ##copies).  However,
 109 ! copy-propagation will remove the ##copies that
 110 ! value-numbering introduces.  So, a band-aid solution is to
 111 ! suffix a predecessors-changed to copy-propagation, so that
 112 ! future calls to needs-predecessors (particularly in
 113 ! compiler.cfg.dce:eliminate-dead-code) will finally correct
 114 ! the ##phi nodes left over after value-numbering.
 115 !
 116 ! A better solution (and the eventual goal) would be to have
 117 ! value-numbering subsume copy-propagation, thus eliminating
 118 ! this pass altogether.
 119
 120 USE: compiler.cfg
 121
 122 : copy-propagation ( cfg -- )
 123     {
 124         needs-predecessors
 125         collect-copies
 126         rename-copies
 127         predecessors-changed
 128     } apply-passes ;