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