basis/compiler/cfg/value-numbering/value-numbering.factor

   1 ! Copyright (C) 2008, 2010 Slava Pestov.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: accessors arrays assocs compiler.cfg compiler.cfg.def-use
   4 compiler.cfg.instructions compiler.cfg.rpo
   5 compiler.cfg.utilities kernel locals namespaces sequences
   6 sequences.deep ;
   7
   8 USE: compiler.cfg.value-numbering.alien
   9 USE: compiler.cfg.value-numbering.comparisons
  10 USE: compiler.cfg.value-numbering.expressions
  11 USE: compiler.cfg.value-numbering.folding
  12 USE: compiler.cfg.value-numbering.graph
  13 USE: compiler.cfg.value-numbering.math
  14 USE: compiler.cfg.value-numbering.misc
  15 USE: compiler.cfg.value-numbering.rewrite
  16 USE: compiler.cfg.value-numbering.slots
  17
  18 IN: compiler.cfg.value-numbering
  19
  20 GENERIC: process-instruction ( insn -- insn' )
  21
  22 : redundant-instruction ( insn vn -- insn' )
  23     [ dst>> ] dip [ swap set-vn ] [ <copy> ] 2bi ;
  24
  25 :: useful-instruction ( insn expr -- insn' )
  26     insn dst>> :> vn
  27     vn vn vregs>vns get set-at
  28     vn expr exprs>vns get set-at
  29     insn vn vns>insns get set-at
  30     insn ;
  31
  32 : check-redundancy ( insn -- insn' )
  33     dup >expr dup exprs>vns get at
  34     [ redundant-instruction ] [ useful-instruction ] ?if ;
  35
  36 M: insn process-instruction
  37     dup rewrite [ process-instruction ] [ ] ?if ;
  38
  39 M: foldable-insn process-instruction
  40     dup rewrite
  41     [ process-instruction ]
  42     [ dup defs-vregs length 1 = [ check-redundancy ] when ] ?if ;
  43
  44 M: ##copy process-instruction
  45     dup [ src>> vreg>vn ] [ dst>> ] bi set-vn ;
  46
  47 M: array process-instruction
  48     [ process-instruction ] map ;
  49
  50 : value-numbering-step ( insns -- insns' )
  51     init-value-graph
  52     [ process-instruction ] map flatten ;
  53
  54 : value-numbering ( cfg -- )
  55     [ [ value-numbering-step ] simple-optimization ]
  56     [ cfg-changed ]
  57     [ predecessors-changed ] tri ;