basis/compiler/cfg/linear-scan/live-intervals/live-intervals.factor

   1 ! Copyright (C) 2008, 2010 Slava Pestov.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: accessors assocs binary-search combinators
   4 compiler.cfg.def-use compiler.cfg.instructions
   5 compiler.cfg.linear-scan.ranges compiler.cfg.linearization
   6 compiler.cfg.liveness compiler.cfg.registers
   7 compiler.cfg.ssa.destruction.leaders cpu.architecture kernel
   8 math math.order namespaces sequences vectors ;
   9 IN: compiler.cfg.linear-scan.live-intervals
  10
  11 TUPLE: vreg-use n def-rep use-rep spill-slot? ;
  12
  13 : <vreg-use> ( n -- vreg-use ) vreg-use new swap >>n ;
  14
  15 TUPLE: live-interval-state
  16     vreg
  17     reg spill-to spill-rep reload-from reload-rep
  18     { ranges vector } { uses vector } ;
  19
  20 : first-use ( live-interval -- use ) uses>> first ; inline
  21
  22 : last-use ( live-interval -- use ) uses>> last ; inline
  23
  24 : new-use ( insn# uses -- use )
  25     [ <vreg-use> dup ] dip push ;
  26
  27 : last-use? ( insn# uses -- use/f )
  28     [ drop f ] [ last [ n>> = ] keep and ] if-empty ;
  29
  30 :: (add-use) ( insn# live-interval spill-slot? -- use )
  31     live-interval uses>> :> uses
  32     insn# uses last-use? [ insn# uses new-use ] unless*
  33     spill-slot? [ t >>spill-slot? ] when ;
  34
  35 : (find-use) ( insn# live-interval -- vreg-use )
  36     uses>> [ n>> <=> ] with search nip ;
  37
  38 :: find-use ( insn# live-interval -- vreg-use/f )
  39     insn# live-interval (find-use)
  40     [ dup n>> insn# = [ drop f ] unless ] ?call ;
  41
  42 : <live-interval> ( vreg -- live-interval )
  43     \ live-interval-state new
  44         V{ } clone >>uses
  45         V{ } clone >>ranges
  46         swap >>vreg ;
  47
  48 : block-from ( bb -- n ) instructions>> first insn#>> 1 - ;
  49
  50 : block-to ( bb -- n ) instructions>> last insn#>> ;
  51
  52 SYMBOLS: from to ;
  53
  54 SYMBOL: live-intervals
  55
  56 : vreg>live-interval ( vreg -- live-interval )
  57     leader live-intervals get [ <live-interval> ] cache ;
  58
  59 : interval-reg-class ( live-interval -- reg-class )
  60     vreg>> rep-of reg-class-of ;
  61
  62 GENERIC: compute-live-intervals* ( insn -- )
  63
  64 M: insn compute-live-intervals* drop ;
  65
  66 :: record-def ( vreg n spill-slot? -- )
  67     vreg vreg>live-interval :> live-interval
  68
  69     n live-interval ranges>> shorten-ranges
  70     n live-interval spill-slot? (add-use) vreg rep-of >>def-rep drop ;
  71
  72 :: record-use ( vreg n spill-slot? -- )
  73     vreg vreg>live-interval :> live-interval
  74
  75     from get n live-interval ranges>> add-range
  76     n live-interval spill-slot? (add-use) vreg rep-of >>use-rep drop ;
  77
  78 :: record-temp ( vreg n -- )
  79     vreg vreg>live-interval :> live-interval
  80
  81     n n live-interval ranges>> add-range
  82     n live-interval f (add-use) vreg rep-of >>def-rep drop ;
  83
  84 : uses-vregs* ( insn -- seq )
  85     dup gc-map-insn? [
  86         [ uses-vregs ] [ gc-map>> derived-roots>> values ] bi append
  87     ] [ uses-vregs ] if ;
  88
  89 UNION: hairy-clobber-insn
  90     alien-call-insn
  91     ##callback-inputs
  92     ##callback-outputs
  93     ##unbox-long-long ;
  94
  95 UNION: clobber-insn
  96     hairy-clobber-insn
  97     ##unbox
  98     ##box
  99     ##box-long-long ;
 100
 101 M: vreg-insn compute-live-intervals* ( insn -- )
 102     dup insn#>>
 103     [ [ defs-vregs ] dip '[ _ f record-def ] each ]
 104     [ [ uses-vregs* ] dip '[ _ f record-use ] each ]
 105     [ [ temp-vregs ] dip '[ _ record-temp ] each ]
 106     2tri ;
 107
 108 M: clobber-insn compute-live-intervals* ( insn -- )
 109     dup insn#>>
 110     [ [ defs-vregs ] dip '[ _ f record-def ] each ]
 111     [ [ uses-vregs* ] dip '[ _ t record-use ] each ]
 112     [ [ temp-vregs ] dip '[ _ record-temp ] each ]
 113     2tri ;
 114
 115 M: hairy-clobber-insn compute-live-intervals* ( insn -- )
 116     dup insn#>>
 117     [ [ defs-vregs ] dip '[ _ t record-def ] each ]
 118     [ [ uses-vregs* ] dip '[ _ t record-use ] each ]
 119     [ [ temp-vregs ] dip '[ _ record-temp ] each ]
 120     2tri ;
 121
 122 : handle-live-out ( bb -- )
 123     [ from get to get ] dip live-out keys
 124     [ vreg>live-interval ranges>> add-range ] 2with each ;
 125
 126 : compute-live-intervals-step ( bb -- )
 127     {
 128         [ block-from from set ]
 129         [ block-to to set ]
 130         [ handle-live-out ]
 131         [ instructions>> <reversed> [ compute-live-intervals* ] each ]
 132     } cleave ;
 133
 134 : live-interval-start ( live-interval -- n )
 135     ranges>> first first ; inline
 136
 137 : live-interval-end ( live-interval -- n )
 138     ranges>> last last ; inline
 139
 140 ERROR: bad-live-interval live-interval ;
 141
 142 : check-start ( live-interval -- )
 143     dup live-interval-start -1 = [ bad-live-interval ] [ drop ] if ;
 144
 145 : finish-live-interval ( live-interval -- )
 146     [ ranges>> reverse! ] [ uses>> reverse! ] [ check-start ] tri 2drop ;
 147
 148 TUPLE: sync-point n keep-dst? ;
 149
 150 GENERIC: insn>sync-point ( insn -- sync-point/f )
 151
 152 M: clobber-insn insn>sync-point
 153     [ insn#>> ] [ hairy-clobber-insn? not ] bi sync-point boa ;
 154
 155 M: insn insn>sync-point drop f ;
 156
 157 : cfg>sync-points ( cfg -- sync-points )
 158     cfg>insns [ insn>sync-point ] map sift ;
 159
 160 : cfg>live-intervals ( cfg -- live-intervals )
 161     H{ } clone live-intervals set
 162     linearization-order <reversed> [ compute-live-intervals-step ] each
 163     live-intervals get values dup [ finish-live-interval ] each ;
 164
 165 : compute-live-intervals ( cfg -- intervals/sync-points )
 166     [ cfg>live-intervals ] [ cfg>sync-points ] bi append ;
 167
 168 : intersect-intervals ( interval1 interval2 -- n/f )
 169     [ ranges>> ] bi@ intersect-ranges ;
 170
 171 : intervals-intersect? ( interval1 interval2 -- ? )
 172     intersect-intervals >boolean ; inline