basis/compiler/cfg/linear-scan/allocation/splitting/splitting.factor

   1 ! Copyright (C) 2009, 2010 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors binary-search combinators
   4 compiler.cfg.linear-scan.allocation.state
   5 compiler.cfg.linear-scan.live-intervals fry hints kernel locals
   6 math math.order namespaces sequences ;
   7 IN: compiler.cfg.linear-scan.allocation.splitting
   8
   9 : split-range ( live-range n -- before after )
  10     [ [ from>> ] dip <live-range> ]
  11     [ 1 + swap to>> <live-range> ]
  12     2bi ;
  13
  14 : split-last-range? ( last n -- ? )
  15     swap to>> <= ;
  16
  17 : split-last-range ( before after last n -- before' after' )
  18     split-range [ [ but-last ] dip suffix ] [ prefix ] bi-curry* bi* ;
  19
  20 : split-ranges ( live-ranges n -- before after )
  21     [ '[ from>> _ <= ] partition ]
  22     [
  23         [ over last ] dip 2dup split-last-range?
  24         [ split-last-range ] [ 2drop ] if
  25     ] bi ;
  26
  27 :: split-uses ( uses n -- before after )
  28     uses n uses [ n>> <=> ] with search
  29     n>> n <=> {
  30         { +eq+ [ [ head-slice ] [ 1 + tail-slice ] 2bi ] }
  31         { +lt+ [ 1 + cut-slice ] }
  32         { +gt+ [ cut-slice ] }
  33     } case ;
  34
  35 ERROR: splitting-too-early ;
  36
  37 ERROR: splitting-too-late ;
  38
  39 ERROR: splitting-atomic-interval ;
  40
  41 : check-split ( live-interval n -- )
  42     check-allocation? get [
  43         [ [ start>> ] dip > [ splitting-too-early ] when ]
  44         [ [ end>> ] dip < [ splitting-too-late ] when ]
  45         [ drop [ end>> ] [ start>> ] bi = [ splitting-atomic-interval ] when ]
  46         2tri
  47     ] [ 2drop ] if ; inline
  48
  49 : split-before ( before -- before' )
  50     f >>spill-to ; inline
  51
  52 : split-after ( after -- after' )
  53     f >>reg f >>reload-from ; inline
  54
  55 :: split-interval ( live-interval n -- before after )
  56     live-interval n check-split
  57     live-interval clone :> before
  58     live-interval clone :> after
  59     live-interval uses>> n split-uses before after [ uses<< ] bi-curry@ bi*
  60     live-interval ranges>> n split-ranges before after [ ranges<< ] bi-curry@ bi*
  61     before split-before
  62     after split-after ;
  63
  64 HINTS: split-interval live-interval object ;