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

   1 USING: arrays compiler.cfg.alias-analysis compiler.cfg.instructions
   2 compiler.cfg.registers compiler.cfg.debugger compiler.cfg.comparisons
   3 cpu.architecture tools.test byte-arrays layouts literals alien
   4 accessors sequences ;
   5 IN: compiler.cfg.alias-analysis.tests
   6
   7 : test-alias-analysis ( insn -- insn )
   8     init-alias-analysis
   9     alias-analysis-step
  10     [ f >>insn# ] map ;
  11
  12 ! Redundant load elimination
  13 [
  14     V{
  15         T{ ##peek f 0 D 0 }
  16         T{ ##slot-imm f 1 0 1 0 }
  17         T{ ##copy f 2 1 any-rep }
  18     }
  19 ] [
  20     V{
  21         T{ ##peek f 0 D 0 }
  22         T{ ##slot-imm f 1 0 1 0 }
  23         T{ ##slot-imm f 2 0 1 0 }
  24     } test-alias-analysis
  25 ] unit-test
  26
  27 ! Store-load forwarding
  28 [
  29     V{
  30         T{ ##peek f 0 D 0 }
  31         T{ ##peek f 1 D 1 }
  32         T{ ##set-slot-imm f 1 0 1 0 }
  33         T{ ##copy f 2 1 any-rep }
  34     }
  35 ] [
  36     V{
  37         T{ ##peek f 0 D 0 }
  38         T{ ##peek f 1 D 1 }
  39         T{ ##set-slot-imm f 1 0 1 0 }
  40         T{ ##slot-imm f 2 0 1 0 }
  41     } test-alias-analysis
  42 ] unit-test
  43
  44 ! Dead store elimination
  45 [
  46     V{
  47         T{ ##peek f 0 D 0 }
  48         T{ ##peek f 1 D 1 }
  49         T{ ##peek f 2 D 2 }
  50         T{ ##set-slot-imm f 2 0 1 0 }
  51     }
  52 ] [
  53     V{
  54         T{ ##peek f 0 D 0 }
  55         T{ ##peek f 1 D 1 }
  56         T{ ##peek f 2 D 2 }
  57         T{ ##set-slot-imm f 1 0 1 0 }
  58         T{ ##set-slot-imm f 2 0 1 0 }
  59     } test-alias-analysis
  60 ] unit-test
  61
  62 [
  63     V{
  64         T{ ##peek f 0 D 0 }
  65         T{ ##peek f 1 D 1 }
  66         T{ ##peek f 2 D 2 }
  67         T{ ##peek f 3 D 3 }
  68         T{ ##set-slot-imm f 3 0 1 0 }
  69     }
  70 ] [
  71     V{
  72         T{ ##peek f 0 D 0 }
  73         T{ ##peek f 1 D 1 }
  74         T{ ##peek f 2 D 2 }
  75         T{ ##peek f 3 D 3 }
  76         T{ ##set-slot-imm f 1 0 1 0 }
  77         T{ ##set-slot-imm f 2 0 1 0 }
  78         T{ ##set-slot-imm f 3 0 1 0 }
  79     } test-alias-analysis
  80 ] unit-test
  81
  82 ! Redundant store elimination
  83 [
  84     V{
  85         T{ ##peek f 0 D 0 }
  86         T{ ##slot-imm f 1 0 1 0 }
  87     }
  88 ] [
  89     V{
  90         T{ ##peek f 0 D 0 }
  91         T{ ##slot-imm f 1 0 1 0 }
  92         T{ ##set-slot-imm f 1 0 1 0 }
  93     } test-alias-analysis
  94 ] unit-test
  95
  96 [
  97     V{
  98         T{ ##peek f 0 D 0 }
  99         T{ ##slot-imm f 1 0 1 0 }
 100         T{ ##copy f 2 1 any-rep }
 101     }
 102 ] [
 103     V{
 104         T{ ##peek f 0 D 0 }
 105         T{ ##slot-imm f 1 0 1 0 }
 106         T{ ##copy f 2 1 any-rep }
 107         T{ ##set-slot-imm f 2 0 1 0 }
 108     } test-alias-analysis
 109 ] unit-test
 110
 111 ! Not a redundant load
 112 [
 113     V{
 114         T{ ##peek f 0 D 0 }
 115         T{ ##peek f 1 D 1 }
 116         T{ ##slot-imm f 1 0 1 0 }
 117         T{ ##set-slot-imm f 0 1 1 0 }
 118         T{ ##slot-imm f 2 0 1 0 }
 119     }
 120 ] [
 121     V{
 122         T{ ##peek f 0 D 0 }
 123         T{ ##peek f 1 D 1 }
 124         T{ ##slot-imm f 1 0 1 0 }
 125         T{ ##set-slot-imm f 0 1 1 0 }
 126         T{ ##slot-imm f 2 0 1 0 }
 127     } test-alias-analysis
 128 ] unit-test
 129
 130 ! Not a redundant store
 131 [
 132     V{
 133         T{ ##peek f 0 D 0 }
 134         T{ ##peek f 1 D 1 }
 135         T{ ##peek f 2 D 2 }
 136         T{ ##peek f 3 D 3 }
 137         T{ ##set-slot-imm f 2 1 1 0 }
 138         T{ ##slot-imm f 4 0 1 0 }
 139         T{ ##set-slot-imm f 3 1 1 0 }
 140     }
 141 ] [
 142     V{
 143         T{ ##peek f 0 D 0 }
 144         T{ ##peek f 1 D 1 }
 145         T{ ##peek f 2 D 2 }
 146         T{ ##peek f 3 D 3 }
 147         T{ ##set-slot-imm f 2 1 1 0 }
 148         T{ ##slot-imm f 4 0 1 0 }
 149         T{ ##set-slot-imm f 3 1 1 0 }
 150     } test-alias-analysis
 151 ] unit-test
 152
 153 ! There's a redundant load, but not a redundant store
 154 [
 155     V{
 156         T{ ##peek f 0 D 0 }
 157         T{ ##peek f 1 D 1 }
 158         T{ ##peek f 2 D 2 }
 159         T{ ##peek f 3 D 3 }
 160         T{ ##slot-imm f 4 0 1 0 }
 161         T{ ##set-slot-imm f 2 0 1 0 }
 162         T{ ##slot f 5 0 3 0 0 }
 163         T{ ##set-slot-imm f 3 0 1 0 }
 164         T{ ##copy f 6 3 any-rep }
 165     }
 166 ] [
 167     V{
 168         T{ ##peek f 0 D 0 }
 169         T{ ##peek f 1 D 1 }
 170         T{ ##peek f 2 D 2 }
 171         T{ ##peek f 3 D 3 }
 172         T{ ##slot-imm f 4 0 1 0 }
 173         T{ ##set-slot-imm f 2 0 1 0 }
 174         T{ ##slot f 5 0 3 0 0 }
 175         T{ ##set-slot-imm f 3 0 1 0 }
 176         T{ ##slot-imm f 6 0 1 0 }
 177     } test-alias-analysis
 178 ] unit-test
 179
 180 ! Fresh allocations don't alias existing values
 181
 182 ! Redundant load elimination
 183 [
 184     V{
 185         T{ ##peek f 1 D 1 }
 186         T{ ##peek f 2 D 2 }
 187         T{ ##peek f 3 D 3 }
 188         T{ ##allot f 4 16 array }
 189         T{ ##set-slot-imm f 3 4 1 0 }
 190         T{ ##set-slot-imm f 2 1 1 0 }
 191         T{ ##copy f 5 3 any-rep }
 192     }
 193 ] [
 194     V{
 195         T{ ##peek f 1 D 1 }
 196         T{ ##peek f 2 D 2 }
 197         T{ ##peek f 3 D 3 }
 198         T{ ##allot f 4 16 array }
 199         T{ ##set-slot-imm f 3 4 1 0 }
 200         T{ ##set-slot-imm f 2 1 1 0 }
 201         T{ ##slot-imm f 5 4 1 0 }
 202     } test-alias-analysis
 203 ] unit-test
 204
 205 ! Redundant store elimination
 206 [
 207     V{
 208         T{ ##peek f 1 D 1 }
 209         T{ ##peek f 2 D 2 }
 210         T{ ##peek f 3 D 3 }
 211         T{ ##allot f 4 16 array }
 212         T{ ##slot-imm f 5 1 1 0 }
 213         T{ ##set-slot-imm f 3 4 1 0 }
 214     }
 215 ] [
 216     V{
 217         T{ ##peek f 1 D 1 }
 218         T{ ##peek f 2 D 2 }
 219         T{ ##peek f 3 D 3 }
 220         T{ ##allot f 4 16 array }
 221         T{ ##set-slot-imm f 1 4 1 0 }
 222         T{ ##slot-imm f 5 1 1 0 }
 223         T{ ##set-slot-imm f 3 4 1 0 }
 224     } test-alias-analysis
 225 ] unit-test
 226
 227 ! Storing a new alias class into another object means that heap-ac
 228 ! can now alias the new ac
 229 [
 230     V{
 231         T{ ##peek f 0 D 0 }
 232         T{ ##peek f 1 D 1 }
 233         T{ ##peek f 2 D 2 }
 234         T{ ##peek f 3 D 3 }
 235         T{ ##allot f 4 16 array }
 236         T{ ##set-slot-imm f 0 4 1 0 }
 237         T{ ##set-slot-imm f 4 2 1 0 }
 238         T{ ##slot-imm f 5 3 1 0 }
 239         T{ ##set-slot-imm f 1 5 1 0 }
 240         T{ ##slot-imm f 6 4 1 0 }
 241     }
 242 ] [
 243     V{
 244         T{ ##peek f 0 D 0 }
 245         T{ ##peek f 1 D 1 }
 246         T{ ##peek f 2 D 2 }
 247         T{ ##peek f 3 D 3 }
 248         T{ ##allot f 4 16 array }
 249         T{ ##set-slot-imm f 0 4 1 0 }
 250         T{ ##set-slot-imm f 4 2 1 0 }
 251         T{ ##slot-imm f 5 3 1 0 }
 252         T{ ##set-slot-imm f 1 5 1 0 }
 253         T{ ##slot-imm f 6 4 1 0 }
 254     } test-alias-analysis
 255 ] unit-test
 256
 257 ! Compares between objects which cannot alias are eliminated
 258 [
 259     V{
 260         T{ ##peek f 0 D 0 }
 261         T{ ##allot f 1 16 array }
 262         T{ ##load-reference f 2 f }
 263     }
 264 ] [
 265     V{
 266         T{ ##peek f 0 D 0 }
 267         T{ ##allot f 1 16 array }
 268         T{ ##compare f 2 0 1 cc= }
 269     } test-alias-analysis
 270 ] unit-test
 271
 272 ! Make sure that input to ##box-displaced-alien becomes heap-ac
 273 [
 274     V{
 275         T{ ##allot f 1 16 byte-array }
 276         T{ ##load-reference f 2 10 }
 277         T{ ##box-displaced-alien f 3 2 1 4 byte-array }
 278         T{ ##slot-imm f 5 3 1 $[ alien type-number ] }
 279         T{ ##compare f 6 5 1 cc= }
 280     }
 281 ] [
 282     V{
 283         T{ ##allot f 1 16 byte-array }
 284         T{ ##load-reference f 2 10 }
 285         T{ ##box-displaced-alien f 3 2 1 4 byte-array }
 286         T{ ##slot-imm f 5 3 1 $[ alien type-number ] }
 287         T{ ##compare f 6 5 1 cc= }
 288     } test-alias-analysis
 289 ] unit-test
 290
 291 ! We can't make any assumptions about heap-ac between
 292 ! instructions which can call back into Factor code
 293 [
 294     V{
 295         T{ ##peek f 0 D 0 }
 296         T{ ##slot-imm f 1 0 1 0 }
 297         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 298         T{ ##slot-imm f 2 0 1 0 }
 299     }
 300 ] [
 301     V{
 302         T{ ##peek f 0 D 0 }
 303         T{ ##slot-imm f 1 0 1 0 }
 304         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 305         T{ ##slot-imm f 2 0 1 0 }
 306     } test-alias-analysis
 307 ] unit-test
 308
 309 [
 310     V{
 311         T{ ##peek f 0 D 0 }
 312         T{ ##peek f 1 D 1 }
 313         T{ ##set-slot-imm f 1 0 1 0 }
 314         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 315         T{ ##slot-imm f 2 0 1 0 }
 316     }
 317 ] [
 318     V{
 319         T{ ##peek f 0 D 0 }
 320         T{ ##peek f 1 D 1 }
 321         T{ ##set-slot-imm f 1 0 1 0 }
 322         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 323         T{ ##slot-imm f 2 0 1 0 }
 324     } test-alias-analysis
 325 ] unit-test
 326
 327 [
 328     V{
 329         T{ ##peek f 0 D 0 }
 330         T{ ##peek f 1 D 1 }
 331         T{ ##peek f 2 D 2 }
 332         T{ ##set-slot-imm f 1 0 1 0 }
 333         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 334         T{ ##set-slot-imm f 2 0 1 0 }
 335     }
 336 ] [
 337     V{
 338         T{ ##peek f 0 D 0 }
 339         T{ ##peek f 1 D 1 }
 340         T{ ##peek f 2 D 2 }
 341         T{ ##set-slot-imm f 1 0 1 0 }
 342         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 343         T{ ##set-slot-imm f 2 0 1 0 }
 344     } test-alias-analysis
 345 ] unit-test
 346
 347 [
 348     V{
 349         T{ ##peek f 0 D 0 }
 350         T{ ##slot-imm f 1 0 1 0 }
 351         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 352         T{ ##set-slot-imm f 1 0 1 0 }
 353     }
 354 ] [
 355     V{
 356         T{ ##peek f 0 D 0 }
 357         T{ ##slot-imm f 1 0 1 0 }
 358         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 359         T{ ##set-slot-imm f 1 0 1 0 }
 360     } test-alias-analysis
 361 ] unit-test
 362
 363 ! We can't eliminate stores on any alias class across a GC-ing
 364 ! instruction
 365 [
 366     V{
 367         T{ ##allot f 0 }
 368         T{ ##slot-imm f 1 0 1 0 }
 369         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 370         T{ ##copy f 2 1 any-rep }
 371     }
 372 ] [
 373     V{
 374         T{ ##allot f 0 }
 375         T{ ##slot-imm f 1 0 1 0 }
 376         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 377         T{ ##slot-imm f 2 0 1 0 }
 378     } test-alias-analysis
 379 ] unit-test
 380
 381 [
 382     V{
 383         T{ ##allot f 0 }
 384         T{ ##peek f 1 D 1 }
 385         T{ ##set-slot-imm f 1 0 1 0 }
 386         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 387         T{ ##copy f 2 1 any-rep }
 388     }
 389 ] [
 390     V{
 391         T{ ##allot f 0 }
 392         T{ ##peek f 1 D 1 }
 393         T{ ##set-slot-imm f 1 0 1 0 }
 394         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 395         T{ ##slot-imm f 2 0 1 0 }
 396     } test-alias-analysis
 397 ] unit-test
 398
 399 [
 400     V{
 401         T{ ##allot f 0 }
 402         T{ ##peek f 1 D 1 }
 403         T{ ##peek f 2 D 2 }
 404         T{ ##set-slot-imm f 1 0 1 0 }
 405         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 406         T{ ##set-slot-imm f 2 0 1 0 }
 407     }
 408 ] [
 409     V{
 410         T{ ##allot f 0 }
 411         T{ ##peek f 1 D 1 }
 412         T{ ##peek f 2 D 2 }
 413         T{ ##set-slot-imm f 1 0 1 0 }
 414         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 415         T{ ##set-slot-imm f 2 0 1 0 }
 416     } test-alias-analysis
 417 ] unit-test
 418
 419 [
 420     V{
 421         T{ ##allot f 0 }
 422         T{ ##slot-imm f 1 0 1 0 }
 423         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 424     }
 425 ] [
 426     V{
 427         T{ ##allot f 0 }
 428         T{ ##slot-imm f 1 0 1 0 }
 429         T{ ##alien-invoke f { } { } { } { } 0 0 "free" }
 430         T{ ##set-slot-imm f 1 0 1 0 }
 431     } test-alias-analysis
 432 ] unit-test
 433
 434 ! Make sure that gc-map-insns which are also vreg-insns are
 435 ! handled properly
 436 [
 437     V{
 438         T{ ##allot f 0 }
 439         T{ ##alien-indirect f { } { } { { 2 double-rep 0 } } { } 0 0 "free" }
 440         T{ ##set-slot-imm f 2 0 1 0 }
 441     }
 442 ] [
 443     V{
 444         T{ ##allot f 0 }
 445         T{ ##alien-indirect f { } { } { { 2 double-rep 0 } } { } 0 0 "free" }
 446         T{ ##set-slot-imm f 2 0 1 0 }
 447     } test-alias-analysis
 448 ] unit-test