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

   1 ! Copyright (C) 2009 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors assocs combinators combinators.short-circuit
   4 kernel math namespaces sequences locals compiler.cfg.def-use
   5 compiler.cfg.dominance compiler.cfg.ssa.destruction.live-ranges ;
   6 IN: compiler.cfg.ssa.destruction.interference
   7
   8 <PRIVATE
   9
  10 : kill-after-def? ( vreg1 vreg2 bb -- ? )
  11     ! If first register is used after second one is defined, they interfere.
  12     ! If they are used in the same instruction, no interference. If the
  13     ! instruction is a def-is-use-insn, then there will be a use at +1
  14     ! (instructions are 2 apart) and so outputs will interfere with
  15     ! inputs.
  16     [ kill-index ] [ def-index ] bi-curry bi* > ;
  17
  18 : interferes-same-block? ( vreg1 vreg2 bb1 bb2 -- ? )
  19     ! If both are defined in the same basic block, they interfere if their
  20     ! local live ranges intersect.
  21     drop
  22     { [ kill-after-def? ] [ swapd kill-after-def? ] } 3|| ;
  23
  24 : interferes-first-dominates? ( vreg1 vreg2 bb1 bb2 -- ? )
  25     ! If vreg1 dominates vreg2, then they interfere if vreg2's definition
  26     ! occurs before vreg1 is killed.
  27     nip
  28     kill-after-def? ;
  29
  30 : interferes-second-dominates? ( vreg1 vreg2 bb1 bb2 -- ? )
  31     ! If vreg2 dominates vreg1, then they interfere if vreg1's definition
  32     ! occurs before vreg2 is killed.
  33     drop
  34     swapd kill-after-def? ;
  35
  36 PRIVATE>
  37
  38 : interferes? ( vreg1 vreg2 -- ? )
  39     2dup [ def-of ] bi@ {
  40         { [ 2dup eq? ] [ interferes-same-block? ] }
  41         { [ 2dup dominates? ] [ interferes-first-dominates? ] }
  42         { [ 2dup swap dominates? ] [ interferes-second-dominates? ] }
  43         [ 2drop 2drop f ]
  44     } cond ;