basis/compiler/cfg/liveness/liveness-tests.factor

   1 USING: accessors alien assocs compiler.cfg compiler.cfg.comparisons
   2 compiler.cfg.def-use compiler.cfg.instructions compiler.cfg.liveness
   3 compiler.cfg.registers compiler.cfg.ssa.destruction.leaders
   4 compiler.cfg.utilities compiler.test compiler.utilities cpu.architecture
   5 cpu.x86.assembler.operands kernel math namespaces sequences system
   6 tools.test ;
   7 IN: compiler.cfg.liveness.tests
   8
   9 ! compute-edge-live-in
  10 { H{ } } [
  11     { } 0 insns>block compute-edge-live-in
  12 ] unit-test
  13
  14 {
  15     H{
  16         { "bl1" H{ { 7 7 } } }
  17         { "bl2" H{ { 99 99 } } }
  18     }
  19 } [
  20     {
  21         T{ ##phi
  22            { dst 103 }
  23            { inputs H{ { "bl1" 7 } { "bl2" 99 } } }
  24         }
  25     } 0 insns>block
  26     compute-edge-live-in
  27 ] unit-test
  28
  29 {
  30     H{
  31         { "b-31" H{ { 192 192 } { 193 193 } { 194 194 } { 195 195 } } }
  32         { "b-23" H{ { 181 181 } { 182 182 } { 183 183 } { 187 187 } } }
  33         { "b-26" H{ { 188 188 } { 189 189 } { 190 190 } { 191 191 } } }
  34     }
  35 } [
  36     {
  37         T{ ##phi
  38            { dst 196 }
  39            { inputs H{ { "b-26" 189 } { "b-23" 183 } { "b-31" 193 } } }
  40         }
  41         T{ ##phi
  42            { dst 197 }
  43            { inputs H{ { "b-26" 190 } { "b-23" 182 } { "b-31" 194 } } }
  44         }
  45         T{ ##phi
  46            { dst 198 }
  47            { inputs H{ { "b-26" 191 } { "b-23" 181 } { "b-31" 195 } } }
  48         }
  49         T{ ##phi
  50            { dst 199 }
  51            { inputs H{ { "b-26" 188 } { "b-23" 187 } { "b-31" 192 } } }
  52         }
  53     } 0 insns>block compute-edge-live-in
  54 ] unit-test
  55
  56 ! fill-gc-map
  57 {
  58     T{ gc-map { gc-roots { 48 } } { derived-roots V{ } } }
  59 } [
  60     H{ { 48 tagged-rep } } representations set
  61     H{ { 48 48  } } clone
  62     T{ gc-map } [ fill-gc-map ] keep
  63 ] unit-test
  64
  65 ! gc-roots
  66 ! only vregs that are tagged are real gc roots
  67 { V{ } { 125 } } [
  68     H{
  69         { 123 double-rep }
  70         { 124 double-2-rep }
  71         { 125 tagged-rep }
  72     } representations set
  73     { 123 124 125 } unique gc-roots
  74 ] unit-test
  75
  76 ! gen-uses
  77 { H{ { 37 37 } } } [
  78     H{ } clone [ T{ ##replace f 37 D: 0 0 } gen-uses ] keep
  79 ] unit-test
  80
  81 ! kill-defs
  82 { H{ } } [
  83     H{ } dup T{ ##peek f 37 D: 0 0 } kill-defs
  84 ] unit-test
  85
  86 { H{ { 3 3 } } } [
  87     H{ { 37 99 } { 99 99 } { 2 99 } } leader-map set
  88     H{ { 37 37 } { 3 3 } } dup T{ ##peek f 2 D: 0 0 } kill-defs
  89 ] unit-test
  90
  91 ! liveness-step
  92 { 3 } [
  93     init-liveness
  94     3 <iota> [ <basic-block> swap >>number ] map <basic-block>
  95     [ connect-Nto1-bbs ] keep liveness-step length
  96 ] unit-test
  97
  98 ! lookup-base-pointer
  99 { 84 } [
 100     H{ { 84 84 } } clone base-pointers set 84 lookup-base-pointer
 101 ] unit-test
 102
 103 { 15 } [
 104     { T{ ##tagged>integer f 30 15 } } 0 insns>block block>cfg compute-live-sets
 105     30 lookup-base-pointer
 106 ] unit-test
 107
 108 cpu x86.64? [
 109     { f } [
 110         H{ } base-pointers set
 111         H{ { 123 T{ ##peek { dst RCX } { loc D: 1 } { insn# 6 } } } } insns set
 112         123 lookup-base-pointer
 113     ] unit-test
 114 ] when
 115
 116 ! lookup-base-pointer*
 117 { f } [
 118     456 T{ ##peek f 123 D: 0 } lookup-base-pointer*
 119 ] unit-test
 120
 121 ! transfer-liveness
 122 {
 123     H{ { 37 37 } }
 124 } [
 125     H{ } clone dup { T{ ##replace f 37 D: 1 6 } T{ ##peek f 37 D: 0 0 } }
 126     transfer-liveness
 127 ] unit-test
 128
 129 ! visit-gc-root
 130 { V{ } HS{ 48 } } [
 131     H{ { 48 tagged-rep } } representations set
 132     48 V{ } clone HS{ } clone [ visit-gc-root ] 2keep
 133 ] unit-test
 134
 135 ! So the real root is 40?
 136 { V{ { 48 40 } } HS{ 40 } } [
 137     H{ { 48 40 } } base-pointers set
 138     H{ { 48 int-rep } } representations set
 139     48 V{ } clone HS{ } clone [ visit-gc-root ] 2keep
 140 ] unit-test
 141
 142 ! visit-insn
 143 { H{ } } [
 144     H{ } clone [ T{ ##peek f 0 D: 0 } visit-insn ] keep
 145 ] unit-test
 146
 147 { H{ { 48 48 } { 37 37 } } } [
 148     H{ { 48 tagged-rep } } representations set
 149     H{ { 48 48  } } clone [ T{ ##replace f 37 D: 1 6 } visit-insn ] keep
 150 ] unit-test
 151
 152 {
 153     T{ ##call-gc
 154        { gc-map
 155          T{ gc-map { gc-roots { 93 } } { derived-roots V{ } } }
 156        }
 157     }
 158 } [
 159     H{ { 93 tagged-rep } } representations set
 160     H{ { 93 93  } } clone T{ ##call-gc f T{ gc-map } }
 161     [ visit-insn ] keep
 162 ] unit-test
 163
 164 : test-liveness ( -- )
 165     1 get block>cfg compute-live-sets ;
 166
 167 ! Sanity check...
 168
 169 V{
 170     T{ ##peek f 0 D: 0 }
 171     T{ ##replace f 0 D: 0 }
 172     T{ ##replace f 1 D: 1 }
 173     T{ ##peek f 1 D: 1 }
 174     T{ ##branch }
 175 } 1 test-bb
 176
 177 V{
 178     T{ ##replace f 2 D: 0 }
 179     T{ ##branch }
 180 } 2 test-bb
 181
 182 V{
 183     T{ ##replace f 3 D: 0 }
 184     T{ ##return }
 185 } 3 test-bb
 186
 187 1 { 2 3 } edges
 188
 189 { } [ test-liveness ] unit-test
 190
 191 {
 192     H{
 193         { 1 1 }
 194         { 2 2 }
 195         { 3 3 }
 196     }
 197 }
 198 [ 1 get live-in ]
 199 unit-test
 200
 201 ! Tricky case; defs must be killed before uses
 202
 203 V{
 204     T{ ##peek f 0 D: 0 }
 205     T{ ##branch }
 206 } 1 test-bb
 207
 208 V{
 209     T{ ##add-imm f 0 0 10 }
 210     T{ ##return }
 211 } 2 test-bb
 212
 213 1 2 edge
 214
 215 { } [ test-liveness ] unit-test
 216
 217 { H{ { 0 0 } } } [ 2 get live-in ] unit-test
 218
 219 ! Regression
 220 V{
 221     T{ ##prologue }
 222     T{ ##branch }
 223 } 0 test-bb
 224
 225 V{
 226     T{ ##inc { loc R: 2 } }
 227     T{ ##inc { loc D: -2 } }
 228     T{ ##peek f 21 D: -1 }
 229     T{ ##peek f 22 D: -2 }
 230     T{ ##replace f 21 R: 0 }
 231     T{ ##replace f 22 R: 1 }
 232     T{ ##branch }
 233 } 1 test-bb
 234
 235 V{
 236     T{ ##call f >c-ptr }
 237     T{ ##branch }
 238 } 2 test-bb
 239
 240 V{
 241     T{ ##inc { loc R: -1 } }
 242     T{ ##inc { loc D: 1 } }
 243     T{ ##peek f 25 R: -1 }
 244     T{ ##replace f 25 D: 0 }
 245     T{ ##branch }
 246 } 3 test-bb
 247
 248 V{
 249     T{ ##call f >float }
 250     T{ ##branch }
 251 } 4 test-bb
 252
 253 V{
 254     T{ ##inc f R: -1 }
 255     T{ ##inc f D: 2 }
 256     T{ ##peek f 27 R: -1 }
 257     T{ ##peek f 28 D: 2 }
 258     T{ ##peek f 29 D: 3 }
 259     T{ ##load-integer f 30 1 }
 260     T{ ##load-integer f 31 0 }
 261     T{ ##compare-imm-branch f 27 f cc/= }
 262 } 5 test-bb
 263
 264 V{
 265     T{ ##inc f D: -1 }
 266     T{ ##branch }
 267 } 6 test-bb
 268
 269 V{
 270     T{ ##inc f D: -1 }
 271     T{ ##branch }
 272 } 7 test-bb
 273
 274 V{
 275     T{ ##phi f 36 H{ { 6 30 } { 7 31 } } }
 276     T{ ##inc f D: -2 }
 277     T{ ##unbox f 37 29 "alien_offset" int-rep }
 278     T{ ##unbox f 38 28 "to_double" double-rep }
 279     T{ ##unbox f 39 36 "to_cell" int-rep }
 280     T{ ##alien-invoke f f V{ } V{ { 37 int-rep 0 } { 38 double-rep 4 } { 39 int-rep 12 } } { { 40 int-rep EAX } } { } 0 16 "CFRunLoopRunInMode" f T{ gc-map } }
 281     T{ ##box f 41 40 "from_signed_cell" int-rep T{ gc-map } }
 282     T{ ##replace f 41 D: 0 }
 283     T{ ##branch }
 284 } 8 test-bb
 285
 286 V{
 287     T{ ##epilogue }
 288     T{ ##return }
 289 } 9 test-bb
 290
 291 0 1 edge
 292 1 2 edge
 293 2 3 edge
 294 3 4 edge
 295 4 5 edge
 296 5 { 6 7 } edges
 297 6 8 edge
 298 7 8 edge
 299 8 9 edge
 300
 301 { } [ test-liveness ] unit-test
 302
 303 { H{ { 28 28 } { 29 29 } { 30 30 } { 31 31 } } } [ 5 get live-out ] unit-test
 304 { H{ { 28 28 } { 29 29 } { 30 30 } } } [ 6 get live-in ] unit-test
 305 { H{ { 28 28 } { 29 29 } { 31 31 } } } [ 7 get live-in ] unit-test
 306 { H{ { 30 30 } } } [ 6 get 8 get edge-live-in ] unit-test
 307
 308 V{
 309     T{ ##prologue }
 310     T{ ##branch }
 311 } 0 test-bb
 312
 313 V{
 314     T{ ##branch }
 315 } 1 test-bb
 316
 317 V{
 318     T{ ##load-integer f 0 0 }
 319     T{ ##branch }
 320 } 2 test-bb
 321
 322 V{
 323     T{ ##load-integer f 1 1 }
 324     T{ ##branch }
 325 } 3 test-bb
 326
 327 V{
 328     T{ ##phi f 2 H{ { 2 0 } { 3 1 } } }
 329     T{ ##branch }
 330 } 4 test-bb
 331
 332 V{
 333     T{ ##branch }
 334 } 5 test-bb
 335
 336 V{
 337     T{ ##replace f 2 D: 0 }
 338     T{ ##branch }
 339 } 6 test-bb
 340
 341 V{
 342     T{ ##epilogue }
 343     T{ ##return }
 344 } 7 test-bb
 345
 346 0 1 edge
 347 1 { 2 3 } edges
 348 2 4 edge
 349 3 4 edge
 350 4 { 5 6 } edges
 351 5 6 edge
 352 6 7 edge
 353
 354 { } [ 0 get block>cfg dup cfg set compute-live-sets ] unit-test
 355
 356 { t } [ 0 get live-in assoc-empty? ] unit-test
 357
 358 { H{ { 2 2 } } } [ 4 get live-out ] unit-test
 359
 360 { H{ { 0 0 } } } [ 2 get 4 get edge-live-in ] unit-test
 361
 362 { H{ { 1 1 } } } [ 3 get 4 get edge-live-in ] unit-test
 363
 364
 365 V{
 366     T{ ##prologue }
 367     T{ ##branch }
 368 } 0 test-bb
 369
 370 V{
 371     T{ ##peek f 0 D: 0 }
 372     T{ ##tagged>integer f 1 0 }
 373     T{ ##call-gc f T{ gc-map } }
 374     T{ ##replace f 0 D: 0 }
 375     T{ ##call-gc f T{ gc-map } }
 376     T{ ##replace f 1 D: 0 }
 377     T{ ##branch }
 378 } 1 test-bb
 379
 380 V{
 381     T{ ##epilogue }
 382     T{ ##return }
 383 } 2 test-bb
 384
 385 0 1 edge
 386 1 2 edge
 387
 388 H{
 389     { 0 tagged-rep }
 390     { 1 int-rep }
 391 } representations set
 392
 393 { } [ 0 get block>cfg dup cfg set compute-live-sets ] unit-test
 394
 395 { V{ { 1 0 } } } [ 1 get instructions>> 2 swap nth gc-map>> derived-roots>> ] unit-test
 396
 397 { { 0 } } [ 1 get instructions>> 2 swap nth gc-map>> gc-roots>> ] unit-test
 398
 399 { V{ { 1 0 } } } [ 1 get instructions>> 4 swap nth gc-map>> derived-roots>> ] unit-test
 400
 401 { { 0 } } [ 1 get instructions>> 4 swap nth gc-map>> gc-roots>> ] unit-test