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