basis/compiler/cfg/alias-analysis/alias-analysis.factor

   1 ! Copyright (C) 2008, 2009 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math namespaces assocs hashtables sequences arrays
   4 accessors vectors combinators sets classes cpu.architecture compiler.cfg
   5 compiler.cfg.registers compiler.cfg.instructions
   6 compiler.cfg.copy-prop compiler.cfg.rpo compiler.cfg.liveness ;
   7 IN: compiler.cfg.alias-analysis
   8
   9 ! We try to eliminate redundant slot operations using some simple heuristics.
  10 !
  11 ! All heap-allocated objects which are loaded from the stack, or
  12 ! other object slots are pessimistically assumed to belong to
  13 ! the same alias class.
  14 !
  15 ! Freshly-allocated objects get their own alias class.
  16 !
  17 ! Simple pseudo-C example showing load elimination:
  18 !
  19 ! int *x, *y, z: inputs
  20 ! int a, b, c, d, e: locals
  21 !
  22 ! Before alias analysis:
  23 !
  24 ! a = x[2]
  25 ! b = x[2]
  26 ! c = x[3]
  27 ! y[2] = z
  28 ! d = x[2]
  29 ! e = y[2]
  30 ! f = x[3]
  31 !
  32 ! After alias analysis:
  33 !
  34 ! a = x[2]
  35 ! b = a /* ELIMINATED */
  36 ! c = x[3]
  37 ! y[2] = z
  38 ! d = x[2] /* if x=y, d=z, if x!=y, d=b; NOT ELIMINATED */
  39 ! e = z /* ELIMINATED */
  40 ! f = c /* ELIMINATED */
  41 !
  42 ! Simple pseudo-C example showing store elimination:
  43 !
  44 ! Before alias analysis:
  45 !
  46 ! x[0] = a
  47 ! b = x[n]
  48 ! x[0] = c
  49 ! x[1] = d
  50 ! e = x[0]
  51 ! x[1] = c
  52 !
  53 ! After alias analysis:
  54 !
  55 ! x[0] = a /* dead if n = 0, live otherwise; NOT ELIMINATED */
  56 ! b = x[n]
  57 ! x[0] = c
  58 ! /* x[1] = d */  /* ELIMINATED */
  59 ! e = c
  60 ! x[1] = c
  61
  62 ! Map vregs -> alias classes
  63 SYMBOL: vregs>acs
  64
  65 ERROR: vreg-ac-not-set vreg ;
  66
  67 : vreg>ac ( vreg -- ac )
  68     #! Only vregs produced by ##allot, ##peek and ##slot can
  69     #! ever be used as valid inputs to ##slot and ##set-slot,
  70     #! so we assert this fact by not giving alias classes to
  71     #! other vregs.
  72     vregs>acs get ?at [ vreg-ac-not-set ] unless ;
  73
  74 ! Map alias classes -> sequence of vregs
  75 SYMBOL: acs>vregs
  76
  77 : ac>vregs ( ac -- vregs ) acs>vregs get at ;
  78
  79 : aliases ( vreg -- vregs )
  80     #! All vregs which may contain the same value as vreg.
  81     vreg>ac ac>vregs ;
  82
  83 : each-alias ( vreg quot -- )
  84     [ aliases ] dip each ; inline
  85
  86 ! Map vregs -> slot# -> vreg
  87 SYMBOL: live-slots
  88
  89 ! Current instruction number
  90 SYMBOL: insn#
  91
  92 ! Load/store history, for dead store elimination
  93 TUPLE: load insn# ;
  94 TUPLE: store insn# ;
  95
  96 : new-action ( class -- action )
  97     insn# get swap boa ; inline
  98
  99 ! Maps vreg -> slot# -> sequence of loads/stores
 100 SYMBOL: histories
 101
 102 : history ( vreg -- history ) histories get at ;
 103
 104 : set-ac ( vreg ac -- )
 105     #! Set alias class of newly-seen vreg.
 106     {
 107         [ drop H{ } clone swap histories get set-at ]
 108         [ drop H{ } clone swap live-slots get set-at ]
 109         [ swap vregs>acs get set-at ]
 110         [ acs>vregs get push-at ]
 111     } 2cleave ;
 112
 113 : live-slot ( slot#/f vreg -- vreg' )
 114     #! If the slot number is unknown, we never reuse a previous
 115     #! value.
 116     over [ live-slots get at at ] [ 2drop f ] if ;
 117
 118 ERROR: vreg-has-no-slots vreg ;
 119
 120 : load-constant-slot ( value slot# vreg -- )
 121     live-slots get ?at [ vreg-has-no-slots ] unless set-at ;
 122
 123 : load-slot ( value slot#/f vreg -- )
 124     over [ load-constant-slot ] [ 3drop ] if ;
 125
 126 : record-constant-slot ( slot# vreg -- )
 127     #! A load can potentially read every store of this slot#
 128     #! in that alias class.
 129     [
 130         history [ load new-action swap ?push ] change-at
 131     ] with each-alias ;
 132
 133 : record-computed-slot ( vreg -- )
 134     #! Computed load is like a load of every slot touched so far
 135     [
 136         history values [ load new-action swap push ] each
 137     ] each-alias ;
 138
 139 : remember-slot ( value slot#/f vreg -- )
 140     over
 141     [ [ record-constant-slot ] [ load-constant-slot ] 2bi ]
 142     [ 2nip record-computed-slot ] if ;
 143
 144 SYMBOL: ac-counter
 145
 146 : next-ac ( -- n )
 147     ac-counter [ dup 1 + ] change ;
 148
 149 ! Alias class for objects which are loaded from the data stack
 150 ! or other object slots. We pessimistically assume that they
 151 ! can all alias each other.
 152 SYMBOL: heap-ac
 153
 154 : set-heap-ac ( vreg -- ) heap-ac get set-ac ;
 155
 156 : set-new-ac ( vreg -- ) next-ac set-ac ;
 157
 158 : kill-constant-set-slot ( slot# vreg -- )
 159     [ live-slots get at delete-at ] with each-alias ;
 160
 161 : record-constant-set-slot ( slot# vreg -- )
 162     history [
 163         dup empty? [ dup last store? [ dup pop* ] when ] unless
 164         store new-action swap ?push
 165     ] change-at ;
 166
 167 : kill-computed-set-slot ( ac -- )
 168     [ live-slots get at clear-assoc ] each-alias ;
 169
 170 : remember-set-slot ( slot#/f vreg -- )
 171     over [
 172         [ record-constant-set-slot ]
 173         [ kill-constant-set-slot ] 2bi
 174     ] [ nip kill-computed-set-slot ] if ;
 175
 176 SYMBOL: constants
 177
 178 : constant ( vreg -- n/f )
 179     #! Return a ##load-immediate value, or f if the vreg was not
 180     #! assigned by an ##load-immediate.
 181     resolve constants get at ;
 182
 183 ! We treat slot accessors and stack traffic alike
 184 GENERIC: insn-slot# ( insn -- slot#/f )
 185 GENERIC: insn-object ( insn -- vreg )
 186
 187 M: ##slot insn-slot# slot>> constant ;
 188 M: ##slot-imm insn-slot# slot>> ;
 189 M: ##set-slot insn-slot# slot>> constant ;
 190 M: ##set-slot-imm insn-slot# slot>> ;
 191 M: ##alien-global insn-slot# [ library>> ] [ symbol>> ] bi 2array ;
 192
 193 M: ##slot insn-object obj>> resolve ;
 194 M: ##slot-imm insn-object obj>> resolve ;
 195 M: ##set-slot insn-object obj>> resolve ;
 196 M: ##set-slot-imm insn-object obj>> resolve ;
 197 M: ##alien-global insn-object drop \ ##alien-global ;
 198
 199 : init-alias-analysis ( insns -- insns' )
 200     H{ } clone histories set
 201     H{ } clone vregs>acs set
 202     H{ } clone acs>vregs set
 203     H{ } clone live-slots set
 204     H{ } clone constants set
 205     H{ } clone copies set
 206
 207     0 ac-counter set
 208     next-ac heap-ac set
 209
 210     dup local-live-in [ set-heap-ac ] each ;
 211
 212 GENERIC: analyze-aliases* ( insn -- insn' )
 213
 214 M: ##load-immediate analyze-aliases*
 215     dup [ val>> ] [ dst>> ] bi constants get set-at ;
 216
 217 M: ##flushable analyze-aliases*
 218     dup dst>> set-heap-ac ;
 219
 220 M: ##allocation analyze-aliases*
 221     #! A freshly allocated object is distinct from any other
 222     #! object.
 223     dup dst>> set-new-ac ;
 224
 225 M: ##read analyze-aliases*
 226     call-next-method
 227     dup [ dst>> ] [ insn-slot# ] [ insn-object ] tri
 228     2dup live-slot dup [
 229         2nip any-rep \ ##copy new-insn analyze-aliases* nip
 230     ] [
 231         drop remember-slot
 232     ] if ;
 233
 234 : idempotent? ( value slot#/f vreg -- ? )
 235     #! Are we storing a value back to the same slot it was read
 236     #! from?
 237     live-slot = ;
 238
 239 M: ##write analyze-aliases*
 240     dup
 241     [ src>> resolve ] [ insn-slot# ] [ insn-object ] tri
 242     [ remember-set-slot drop ] [ load-slot ] 3bi ;
 243
 244 M: ##copy analyze-aliases*
 245     #! The output vreg gets the same alias class as the input
 246     #! vreg, since they both contain the same value.
 247     dup record-copy ;
 248
 249 M: insn analyze-aliases* ;
 250
 251 : analyze-aliases ( insns -- insns' )
 252     [ insn# set analyze-aliases* ] map-index sift ;
 253
 254 SYMBOL: live-stores
 255
 256 : compute-live-stores ( -- )
 257     histories get
 258     values [
 259         values [ [ store? ] filter [ insn#>> ] map ] map concat
 260     ] map concat unique
 261     live-stores set ;
 262
 263 GENERIC: eliminate-dead-stores* ( insn -- insn' )
 264
 265 : (eliminate-dead-stores) ( insn -- insn' )
 266     dup insn-slot# [
 267         insn# get live-stores get key? [
 268             drop f
 269         ] unless
 270     ] when ;
 271
 272 M: ##set-slot eliminate-dead-stores* (eliminate-dead-stores) ;
 273
 274 M: ##set-slot-imm eliminate-dead-stores* (eliminate-dead-stores) ;
 275
 276 M: insn eliminate-dead-stores* ;
 277
 278 : eliminate-dead-stores ( insns -- insns' )
 279     [ insn# set eliminate-dead-stores* ] map-index sift ;
 280
 281 : alias-analysis-step ( insns -- insns' )
 282     init-alias-analysis
 283     analyze-aliases
 284     compute-live-stores
 285     eliminate-dead-stores ;
 286
 287 : alias-analysis ( cfg -- cfg' )
 288     [ alias-analysis-step ] local-optimization ;