1 /** 2 * Code to do the Data Flow Analysis (doesn't act on the data). 3 * 4 * Copyright: Copyright (C) 1985-1998 by Symantec 5 * Copyright (C) 2000-2020 by The D Language Foundation, All Rights Reserved 6 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 7 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 8 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/gflow.d, backend/gflow.d) 9 * Documentation: https://dlang.org/phobos/dmd_backend_gflow.html 10 * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/backend/gflow.d 11 */ 12 13 module dmd.backend.gflow; 14 15 version (SCPP) 16 version = COMPILE; 17 version (MARS) 18 version = COMPILE; 19 20 version (COMPILE) 21 { 22 23 import core.stdc.stdio; 24 import core.stdc.stdlib; 25 import core.stdc.string; 26 27 import dmd.backend.cc; 28 import dmd.backend.cdef; 29 import dmd.backend.code_x86; 30 import dmd.backend.oper; 31 import dmd.backend.global; 32 import dmd.backend.goh; 33 import dmd.backend.el; 34 import dmd.backend.outbuf; 35 import dmd.backend.ty; 36 import dmd.backend.type; 37 38 import dmd.backend.barray; 39 import dmd.backend.dlist; 40 import dmd.backend.dvec; 41 42 nothrow: 43 44 void vec_setclear(size_t b, vec_t vs, vec_t vc) { vec_setbit(b, vs); vec_clearbit(b, vc); } 45 46 bool Eunambig(elem* e) { return OTassign(e.Eoper) && e.EV.E1.Eoper == OPvar; } 47 48 char symbol_isintab(Symbol *s) { return sytab[s.Sclass] & SCSS; } 49 50 void util_free(void* p) { if (p) free(p); } 51 void *util_calloc(uint n, uint size) { void* p = calloc(n, size); assert(!(n * size) || p); return p; } 52 void *util_realloc(void* p, size_t n, size_t size) { void* q = realloc(p, n * size); assert(!(n * size) || q); return q; } 53 54 extern (C++): 55 56 57 /* Since many routines are nearly identical, we can combine them with */ 58 /* this flag: */ 59 60 enum 61 { 62 AE = 1, 63 CP, 64 VBE 65 } 66 67 68 private __gshared 69 { 70 int flowxx; // one of the above values 71 72 vec_t ambigsym = null; 73 } 74 75 76 /***************** REACHING DEFINITIONS *********************/ 77 78 /************************************ 79 * Compute reaching definitions (RDs). 80 * That is, for each block B and each program variable X 81 * find all elems that could be the last elem that defines 82 * X along some path to B. 83 * Binrd = the set of defs reaching the beginning of B. 84 * Boutrd = the set of defs reaching the end of B. 85 * Bkillrd = set of defs that are killed by some def in B. 86 * Bgenrd = set of defs in B that reach the end of B. 87 */ 88 89 void flowrd() 90 { 91 rdgenkill(); /* Compute Bgen and Bkill for RDs */ 92 if (go.defnod.length == 0) /* if no definition elems */ 93 return; /* no analysis to be done */ 94 95 /* The transfer equation is: */ 96 /* Bin = union of Bouts of all predecessors of B. */ 97 /* Bout = (Bin - Bkill) | Bgen */ 98 /* Using Ullman's algorithm: */ 99 100 foreach (b; dfo[]) 101 vec_copy(b.Boutrd, b.Bgen); 102 103 bool anychng; 104 vec_t tmp = vec_calloc(go.defnod.length); 105 do 106 { 107 anychng = false; 108 foreach (b; dfo[]) // for each block 109 { 110 /* Binrd = union of Boutrds of all predecessors of b */ 111 vec_clear(b.Binrd); 112 if (b.BC != BCcatch /*&& b.BC != BCjcatch*/) 113 { 114 /* Set Binrd to 0 to account for: 115 * i = 0; 116 * try { i = 1; throw; } catch () { x = i; } 117 */ 118 foreach (bp; ListRange(b.Bpred)) 119 vec_orass(b.Binrd,list_block(bp).Boutrd); 120 } 121 /* Bout = (Bin - Bkill) | Bgen */ 122 vec_sub(tmp,b.Binrd,b.Bkill); 123 vec_orass(tmp,b.Bgen); 124 if (!anychng) 125 anychng = !vec_equal(tmp,b.Boutrd); 126 vec_copy(b.Boutrd,tmp); 127 } 128 } while (anychng); /* while any changes to Boutrd */ 129 vec_free(tmp); 130 131 static if (0) 132 { 133 dbg_printf("Reaching definitions\n"); 134 foreach (i, b; dfo[]) // for each block 135 { 136 assert(vec_numbits(b.Binrd) == go.defnod.length); 137 dbg_printf("B%d Bin ", cast(int)i); vec_println(b.Binrd); 138 dbg_printf(" Bgen "); vec_println(b.Bgen); 139 dbg_printf(" Bkill "); vec_println(b.Bkill); 140 dbg_printf(" Bout "); vec_println(b.Boutrd); 141 } 142 } 143 } 144 145 /*************************** 146 * Compute Bgen and Bkill for RDs. 147 */ 148 149 private void rdgenkill() 150 { 151 /* Compute number of definition elems. */ 152 uint num_unambig_def = 0; 153 uint deftop = 0; 154 foreach (b; dfo[]) // for each block 155 if (b.Belem) 156 { 157 deftop += numdefelems(b.Belem, &num_unambig_def); 158 } 159 160 /* Allocate array of pointers to all definition elems */ 161 /* The elems are in dfo order. */ 162 /* go.defnod[]s consist of a elem pointer and a pointer */ 163 /* to the enclosing block. */ 164 go.defnod.setLength(deftop); 165 if (deftop == 0) 166 return; 167 168 /* Allocate buffer for the DNunambig vectors 169 */ 170 const size_t dim = (deftop + (VECBITS - 1)) >> VECSHIFT; 171 const sz = (dim + 2) * num_unambig_def; 172 go.dnunambig.setLength(sz); 173 go.dnunambig[] = 0; 174 175 go.defnod.setLength(0); 176 foreach (b; dfo[]) // for each block 177 if (b.Belem) 178 asgdefelems(b, b.Belem); // fill in go.defnod[] 179 assert(go.defnod.length == deftop); 180 181 initDNunambigVectors(); 182 183 foreach (b; dfo[]) // for each block 184 { 185 /* dump any existing vectors */ 186 vec_free(b.Bgen); 187 vec_free(b.Bkill); 188 vec_free(b.Binrd); 189 vec_free(b.Boutrd); 190 191 /* calculate and create new vectors */ 192 rdelem(&(b.Bgen),&(b.Bkill),b.Belem); 193 if (b.BC == BCasm) 194 { 195 vec_clear(b.Bkill); // KILL nothing 196 vec_set(b.Bgen); // GEN everything 197 } 198 b.Binrd = vec_calloc(deftop); 199 b.Boutrd = vec_calloc(deftop); 200 } 201 } 202 203 /********************** 204 * Compute and return # of definition elems in e. 205 */ 206 207 private uint numdefelems(elem *e, uint *pnum_unambig_def) 208 { 209 uint n = 0; 210 while (1) 211 { 212 assert(e); 213 if (OTdef(e.Eoper)) 214 { 215 ++n; 216 if (OTassign(e.Eoper) && e.EV.E1.Eoper == OPvar) 217 ++*pnum_unambig_def; 218 } 219 if (OTbinary(e.Eoper)) 220 { 221 n += numdefelems(e.EV.E1, pnum_unambig_def); 222 e = e.EV.E2; 223 } 224 else if (OTunary(e.Eoper)) 225 { 226 e = e.EV.E1; 227 } 228 else 229 break; 230 } 231 return n; 232 } 233 234 /************************** 235 * Load go.defnod[] array. 236 * Loaded in order of execution of the elems. Not sure if this is 237 * necessary. 238 */ 239 240 private void asgdefelems(block *b,elem *n) 241 { 242 assert(b && n); 243 const op = n.Eoper; 244 if (ERTOL(n)) 245 { 246 asgdefelems(b,n.EV.E2); 247 asgdefelems(b,n.EV.E1); 248 } 249 else if (OTbinary(op)) 250 { 251 asgdefelems(b,n.EV.E1); 252 asgdefelems(b,n.EV.E2); 253 } 254 else if (OTunary(op)) 255 asgdefelems(b,n.EV.E1); 256 if (OTdef(op)) 257 { 258 n.Edef = cast(uint)go.defnod.length; 259 go.defnod.push(DefNode(n, b, null)); 260 } 261 else 262 n.Edef = ~0; // just to ensure it is not in the array 263 } 264 265 /************************************* 266 * Allocate and initialize DNumambig vectors in go.defnod[] 267 */ 268 269 private void initDNunambigVectors() 270 { 271 //printf("initDNunambigVectors()\n"); 272 const size_t numbits = go.defnod.length; 273 const size_t dim = (numbits + (VECBITS - 1)) >> VECSHIFT; 274 275 uint j = 0; 276 foreach (const i; 0 .. go.defnod.length) 277 { 278 elem *e = go.defnod[i].DNelem; 279 if (OTassign(e.Eoper) && e.EV.E1.Eoper == OPvar) 280 { 281 vec_t v = &go.dnunambig[j] + 2; 282 assert(vec_dim(v) == 0); 283 vec_dim(v) = dim; 284 vec_numbits(v) = numbits; 285 j += dim + 2; 286 fillInDNunambig(v, e); 287 go.defnod[i].DNunambig = v; 288 } 289 } 290 assert(j <= go.dnunambig.length); 291 } 292 293 /************************************* 294 * Allocate and compute rd GEN and KILL. 295 */ 296 297 private void rdelem(vec_t *pgen,vec_t *pkill, /* where to put result */ 298 elem *n) /* tree to evaluate for GEN and KILL */ 299 { 300 *pgen = vec_calloc(go.defnod.length); 301 *pkill = vec_calloc(go.defnod.length); 302 if (n) 303 accumrd(*pgen,*pkill,n); 304 } 305 306 /************************************** 307 * Accumulate GEN and KILL vectors for this elem. 308 */ 309 310 private void accumrd(vec_t GEN,vec_t KILL,elem *n) 311 { 312 assert(GEN && KILL && n); 313 const op = n.Eoper; 314 if (OTunary(op)) 315 accumrd(GEN,KILL,n.EV.E1); 316 else if (OTbinary(op)) 317 { 318 if (op == OPcolon || op == OPcolon2) 319 { 320 vec_t Gl,Kl,Gr,Kr; 321 rdelem(&Gl,&Kl,n.EV.E1); 322 rdelem(&Gr,&Kr,n.EV.E2); 323 324 switch (el_returns(n.EV.E1) * 2 | int(el_returns(n.EV.E2))) 325 { 326 case 3: // E1 and E2 return 327 /* GEN = (GEN - Kl) | Gl | 328 * (GEN - Kr) | Gr 329 * KILL |= Kl & Kr 330 * This simplifies to: 331 * GEN = GEN | (Gl | Gr) | (GEN - (Kl & Kr) 332 * KILL |= Kl & Kr 333 */ 334 vec_andass(Kl,Kr); 335 vec_orass(KILL,Kl); 336 337 vec_orass(Gl,Gr); 338 vec_sub(Gr,GEN,Kl); // (GEN - (Kl & Kr) 339 vec_or(GEN,Gl,Gr); 340 break; 341 342 case 2: // E1 returns 343 /* GEN = (GEN - Kl) | Gl 344 * KILL |= Kl 345 */ 346 vec_subass(GEN,Kl); 347 vec_orass(GEN,Gl); 348 vec_orass(KILL,Kl); 349 break; 350 351 case 1: // E2 returns 352 /* GEN = (GEN - Kr) | Gr 353 * KILL |= Kr 354 */ 355 vec_subass(GEN,Kr); 356 vec_orass(GEN,Gr); 357 vec_orass(KILL,Kr); 358 break; 359 360 case 0: // neither returns 361 break; 362 363 default: 364 assert(0); 365 } 366 367 vec_free(Gl); 368 vec_free(Kl); 369 vec_free(Gr); 370 vec_free(Kr); 371 } 372 else if (op == OPandand || op == OPoror) 373 { 374 vec_t Gr,Kr; 375 accumrd(GEN,KILL,n.EV.E1); 376 rdelem(&Gr,&Kr,n.EV.E2); 377 if (el_returns(n.EV.E2)) 378 vec_orass(GEN,Gr); // GEN |= Gr 379 380 vec_free(Gr); 381 vec_free(Kr); 382 } 383 else if (OTrtol(op) && ERTOL(n)) 384 { 385 accumrd(GEN,KILL,n.EV.E2); 386 accumrd(GEN,KILL,n.EV.E1); 387 } 388 else 389 { 390 accumrd(GEN,KILL,n.EV.E1); 391 accumrd(GEN,KILL,n.EV.E2); 392 } 393 } 394 395 if (OTdef(op)) /* if definition elem */ 396 updaterd(n,GEN,KILL); 397 } 398 399 /******************** AVAILABLE EXPRESSIONS ***********************/ 400 401 /************************************ 402 * Compute available expressions (AEs). 403 * That is, expressions whose result is still current. 404 * Bin = the set of AEs reaching the beginning of B. 405 * Bout = the set of AEs reaching the end of B. 406 */ 407 408 void flowae() 409 { 410 flowxx = AE; 411 flowaecp(AE); 412 } 413 414 /**************************** COPY PROPAGATION ************************/ 415 416 /*************************************** 417 * Compute copy propagation info (CPs). 418 * Very similar to AEs (the same code is used). 419 * Using RDs for copy propagation is WRONG! 420 * That is, set of copy statements still valid. 421 * Bin = the set of CPs reaching the beginning of B. 422 * Bout = the set of CPs reaching the end of B. 423 */ 424 425 void flowcp() 426 { 427 flowxx = CP; 428 flowaecp(CP); 429 } 430 431 /***************************************** 432 * Common flow analysis routines for Available Expressions and 433 * Copy Propagation. 434 * Input: 435 * flowxx 436 */ 437 438 private void flowaecp(int flowxx) 439 { 440 aecpgenkill(go, flowxx); // Compute Bgen and Bkill for AEs or CPs 441 if (go.exptop <= 1) /* if no expressions */ 442 return; 443 444 /* The transfer equation is: */ 445 /* Bin = & Bout(all predecessors P of B) */ 446 /* Bout = (Bin - Bkill) | Bgen */ 447 /* Using Ullman's algorithm: */ 448 449 vec_clear(startblock.Bin); 450 vec_copy(startblock.Bout,startblock.Bgen); /* these never change */ 451 if (startblock.BC == BCiftrue) 452 vec_copy(startblock.Bout2,startblock.Bgen2); // these never change 453 454 /* For all blocks except startblock */ 455 foreach (b; dfo[1 .. $]) 456 { 457 vec_set(b.Bin); /* Bin = all expressions */ 458 459 /* Bout = (Bin - Bkill) | Bgen */ 460 vec_sub(b.Bout,b.Bin,b.Bkill); 461 vec_orass(b.Bout,b.Bgen); 462 if (b.BC == BCiftrue) 463 { 464 vec_sub(b.Bout2,b.Bin,b.Bkill2); 465 vec_orass(b.Bout2,b.Bgen2); 466 } 467 } 468 469 vec_t tmp = vec_calloc(go.exptop); 470 bool anychng; 471 do 472 { 473 anychng = false; 474 475 // For all blocks except startblock 476 foreach (b; dfo[1 .. $]) 477 { 478 // Bin = & of Bout of all predecessors 479 // Bout = (Bin - Bkill) | Bgen 480 481 bool first = true; 482 foreach (bl; ListRange(b.Bpred)) 483 { 484 block* bp = list_block(bl); 485 if (bp.BC == BCiftrue && bp.nthSucc(0) != b) 486 { 487 if (first) 488 vec_copy(b.Bin,bp.Bout2); 489 else 490 vec_andass(b.Bin,bp.Bout2); 491 } 492 else 493 { 494 if (first) 495 vec_copy(b.Bin,bp.Bout); 496 else 497 vec_andass(b.Bin,bp.Bout); 498 } 499 first = false; 500 } 501 assert(!first); // it must have had predecessors 502 503 if (b.BC == BCjcatch) 504 { 505 /* Set Bin to 0 to account for: 506 void* pstart = p; 507 try 508 { 509 p = null; // account for this 510 throw; 511 } 512 catch (Throwable o) { assert(p != pstart); } 513 */ 514 vec_clear(b.Bin); 515 } 516 517 if (anychng) 518 { 519 vec_sub(b.Bout,b.Bin,b.Bkill); 520 vec_orass(b.Bout,b.Bgen); 521 } 522 else 523 { 524 vec_sub(tmp,b.Bin,b.Bkill); 525 vec_orass(tmp,b.Bgen); 526 if (!vec_equal(tmp,b.Bout)) 527 { // Swap Bout and tmp instead of 528 // copying tmp over Bout 529 vec_t v = tmp; 530 tmp = b.Bout; 531 b.Bout = v; 532 anychng = true; 533 } 534 } 535 536 if (b.BC == BCiftrue) 537 { // Bout2 = (Bin - Bkill2) | Bgen2 538 if (anychng) 539 { 540 vec_sub(b.Bout2,b.Bin,b.Bkill2); 541 vec_orass(b.Bout2,b.Bgen2); 542 } 543 else 544 { 545 vec_sub(tmp,b.Bin,b.Bkill2); 546 vec_orass(tmp,b.Bgen2); 547 if (!vec_equal(tmp,b.Bout2)) 548 { // Swap Bout and tmp instead of 549 // copying tmp over Bout2 550 vec_t v = tmp; 551 tmp = b.Bout2; 552 b.Bout2 = v; 553 anychng = true; 554 } 555 } 556 } 557 } 558 } while (anychng); 559 vec_free(tmp); 560 } 561 562 563 /*********************************** 564 * Compute Bgen and Bkill for AEs, CPs, and VBEs. 565 */ 566 567 private void aecpgenkill(ref GlobalOptimizer go, int flowxx) 568 { 569 block* this_block; 570 571 /******************************** 572 * Assign cp elems to go.expnod[] (in order of evaluation). 573 */ 574 void asgcpelems(elem *n) 575 { 576 while (1) 577 { 578 const op = n.Eoper; 579 if (OTunary(op)) 580 { 581 n.Eexp = 0; 582 n = n.EV.E1; 583 continue; 584 } 585 else if (OTbinary(op)) 586 { 587 if (ERTOL(n)) 588 { 589 asgcpelems(n.EV.E2); 590 asgcpelems(n.EV.E1); 591 } 592 else 593 { 594 asgcpelems(n.EV.E1); 595 asgcpelems(n.EV.E2); 596 } 597 598 /* look for elem of the form OPvar=OPvar, where they aren't the 599 * same variable. 600 * Don't mix XMM and integer registers. 601 */ 602 elem* e1; 603 elem* e2; 604 if ((op == OPeq || op == OPstreq) && 605 (e1 = n.EV.E1).Eoper == OPvar && 606 (e2 = n.EV.E2).Eoper == OPvar && 607 !((e1.Ety | e2.Ety) & (mTYvolatile | mTYshared)) && 608 (!config.fpxmmregs || 609 (!tyfloating(e1.EV.Vsym.Stype.Tty) == !tyfloating(e2.EV.Vsym.Stype.Tty))) && 610 e1.EV.Vsym != e2.EV.Vsym) 611 { 612 n.Eexp = cast(uint)go.expnod.length; 613 go.expnod.push(n); 614 } 615 else 616 n.Eexp = 0; 617 } 618 else 619 n.Eexp = 0; 620 return; 621 } 622 } 623 624 /******************************** 625 * Assign ae and vbe elems to go.expnod[] (in order of evaluation). 626 */ 627 bool asgaeelems(elem *n) 628 { 629 bool ae; 630 631 assert(n); 632 const op = n.Eoper; 633 if (OTunary(op)) 634 { 635 ae = asgaeelems(n.EV.E1); 636 // Disallow starred references to avoid problems with VBE's 637 // being hoisted before tests of an invalid pointer. 638 if (flowxx == VBE && op == OPind) 639 { 640 n.Eexp = 0; 641 return false; 642 } 643 } 644 else if (OTbinary(op)) 645 { 646 if (ERTOL(n)) 647 ae = asgaeelems(n.EV.E2) & asgaeelems(n.EV.E1); 648 else 649 ae = asgaeelems(n.EV.E1) & asgaeelems(n.EV.E2); 650 } 651 else 652 ae = true; 653 654 if (ae && OTae(op) && !(n.Ety & (mTYvolatile | mTYshared)) && 655 // Disallow struct AEs, because we can't handle CSEs that are structs 656 tybasic(n.Ety) != TYstruct && 657 tybasic(n.Ety) != TYarray) 658 { 659 n.Eexp = cast(uint)go.expnod.length; // remember index into go.expnod[] 660 go.expnod.push(n); 661 if (flowxx == VBE) 662 go.expblk.push(this_block); 663 return true; 664 } 665 else 666 { 667 n.Eexp = 0; 668 return false; 669 } 670 } 671 672 go.expnod.setLength(0); // dump any existing one 673 go.expnod.push(null); 674 675 go.expblk.setLength(0); // dump any existing one 676 go.expblk.push(null); 677 678 foreach (b; dfo[]) 679 { 680 if (b.Belem) 681 { 682 if (flowxx == CP) 683 asgcpelems(b.Belem); 684 else 685 { 686 this_block = b; // so asgaeelems knows about this 687 asgaeelems(b.Belem); 688 } 689 } 690 } 691 go.exptop = cast(uint)go.expnod.length; 692 if (go.exptop <= 1) 693 return; 694 695 defstarkill(); /* compute go.defkill and go.starkill */ 696 697 static if (0) 698 { 699 assert(vec_numbits(go.defkill) == go.expnod.length); 700 assert(vec_numbits(go.starkill) == go.expnod.length); 701 assert(vec_numbits(go.vptrkill) == go.expnod.length); 702 dbg_printf("defkill "); vec_println(go.defkill); 703 if (go.starkill) 704 { dbg_printf("starkill "); vec_println(go.starkill);} 705 if (go.vptrkill) 706 { dbg_printf("vptrkill "); vec_println(go.vptrkill); } 707 } 708 709 foreach (i, b; dfo[]) 710 { 711 /* dump any existing vectors */ 712 vec_free(b.Bin); 713 vec_free(b.Bout); 714 vec_free(b.Bgen); 715 vec_free(b.Bkill); 716 b.Bgen = vec_calloc(go.expnod.length); 717 b.Bkill = vec_calloc(go.expnod.length); 718 switch (b.BC) 719 { 720 case BCiftrue: 721 vec_free(b.Bout2); 722 vec_free(b.Bgen2); 723 vec_free(b.Bkill2); 724 elem* e; 725 for (e = b.Belem; e.Eoper == OPcomma; e = e.EV.E2) 726 accumaecp(b.Bgen,b.Bkill,e.EV.E1); 727 if (e.Eoper == OPandand || e.Eoper == OPoror) 728 { 729 accumaecp(b.Bgen,b.Bkill,e.EV.E1); 730 vec_t Kr = vec_calloc(go.expnod.length); 731 vec_t Gr = vec_calloc(go.expnod.length); 732 accumaecp(Gr,Kr,e.EV.E2); 733 734 // We might or might not have executed E2 735 // KILL1 = KILL | Kr 736 // GEN1 = GEN & ((GEN - Kr) | Gr) 737 738 // We definitely executed E2 739 // KILL2 = (KILL - Gr) | Kr 740 // GEN2 = (GEN - Kr) | Gr 741 742 const uint dim = cast(uint)vec_dim(Kr); 743 vec_t KILL = b.Bkill; 744 vec_t GEN = b.Bgen; 745 746 foreach (j; 0 .. dim) 747 { 748 vec_base_t KILL1 = KILL[j] | Kr[j]; 749 vec_base_t GEN1 = GEN[j] & ((GEN[j] & ~Kr[j]) | Gr[j]); 750 751 vec_base_t KILL2 = (KILL[j] & ~Gr[j]) | Kr[j]; 752 vec_base_t GEN2 = (GEN[j] & ~Kr[j]) | Gr[j]; 753 754 KILL[j] = KILL1; 755 GEN[j] = GEN1; 756 Kr[j] = KILL2; 757 Gr[j] = GEN2; 758 } 759 760 if (e.Eoper == OPandand) 761 { b.Bkill = Kr; 762 b.Bgen = Gr; 763 b.Bkill2 = KILL; 764 b.Bgen2 = GEN; 765 } 766 else 767 { b.Bkill = KILL; 768 b.Bgen = GEN; 769 b.Bkill2 = Kr; 770 b.Bgen2 = Gr; 771 } 772 } 773 else 774 { 775 accumaecp(b.Bgen,b.Bkill,e); 776 b.Bgen2 = vec_clone(b.Bgen); 777 b.Bkill2 = vec_clone(b.Bkill); 778 } 779 b.Bout2 = vec_calloc(go.expnod.length); 780 break; 781 782 case BCasm: 783 vec_set(b.Bkill); // KILL everything 784 vec_clear(b.Bgen); // GEN nothing 785 break; 786 787 default: 788 // calculate GEN & KILL vectors 789 if (b.Belem) 790 accumaecp(b.Bgen,b.Bkill,b.Belem); 791 break; 792 } 793 static if (0) 794 { 795 printf("block %d Bgen ",i); vec_println(b.Bgen); 796 printf(" Bkill "); vec_println(b.Bkill); 797 } 798 b.Bin = vec_calloc(go.expnod.length); 799 b.Bout = vec_calloc(go.expnod.length); 800 } 801 } 802 803 /******************************** 804 * Compute defkill, starkill and vptrkill vectors. 805 * starkill: set of expressions killed when a variable is 806 * changed that somebody could be pointing to. 807 * (not needed for cp) 808 * starkill is a subset of defkill. 809 * defkill: set of expressions killed by an ambiguous 810 * definition. 811 * vptrkill: set of expressions killed by an access to a vptr. 812 */ 813 814 private void defstarkill() 815 { 816 const exptop = go.exptop; 817 vec_recycle(go.defkill, exptop); 818 if (flowxx == CP) 819 { 820 vec_recycle(go.starkill, 0); 821 vec_recycle(go.vptrkill, 0); 822 } 823 else 824 { 825 vec_recycle(go.starkill, exptop); // and create new ones 826 vec_recycle(go.vptrkill, exptop); // and create new ones 827 } 828 829 if (!exptop) 830 return; 831 832 auto defkill = go.defkill; 833 834 if (flowxx == CP) 835 { 836 foreach (i, n; go.expnod[1 .. exptop]) 837 { 838 const op = n.Eoper; 839 assert(op == OPeq || op == OPstreq); 840 assert(n.EV.E1.Eoper==OPvar && n.EV.E2.Eoper==OPvar); 841 842 // Set bit in defkill if either the left or the 843 // right variable is killed by an ambiguous def. 844 845 if (Symbol_isAffected(*n.EV.E1.EV.Vsym) || 846 Symbol_isAffected(*n.EV.E2.EV.Vsym)) 847 { 848 vec_setbit(i + 1,defkill); 849 } 850 } 851 } 852 else 853 { 854 auto starkill = go.starkill; 855 auto vptrkill = go.vptrkill; 856 857 foreach (j, n; go.expnod[1 .. exptop]) 858 { 859 const i = j + 1; 860 const op = n.Eoper; 861 switch (op) 862 { 863 case OPvar: 864 if (Symbol_isAffected(*n.EV.Vsym)) 865 vec_setbit(i,defkill); 866 break; 867 868 case OPind: // if a 'starred' ref 869 if (tybasic(n.EV.E1.Ety) == TYimmutPtr) 870 break; 871 goto case OPstrlen; 872 873 case OPstrlen: 874 case OPstrcmp: 875 case OPmemcmp: 876 case OPbt: // OPbt is like OPind 877 vec_setbit(i,defkill); 878 vec_setbit(i,starkill); 879 break; 880 881 case OPvp_fp: 882 case OPcvp_fp: 883 vec_setbit(i,vptrkill); 884 goto Lunary; 885 886 default: 887 if (OTunary(op)) 888 { 889 Lunary: 890 if (vec_testbit(n.EV.E1.Eexp,defkill)) 891 vec_setbit(i,defkill); 892 if (vec_testbit(n.EV.E1.Eexp,starkill)) 893 vec_setbit(i,starkill); 894 } 895 else if (OTbinary(op)) 896 { 897 if (vec_testbit(n.EV.E1.Eexp,defkill) || 898 vec_testbit(n.EV.E2.Eexp,defkill)) 899 vec_setbit(i,defkill); 900 if (vec_testbit(n.EV.E1.Eexp,starkill) || 901 vec_testbit(n.EV.E2.Eexp,starkill)) 902 vec_setbit(i,starkill); 903 } 904 break; 905 } 906 } 907 } 908 } 909 910 /******************************** 911 * Compute GEN and KILL vectors only for AEs. 912 * defkill and starkill are assumed to be already set up correctly. 913 * go.expnod[] is assumed to be set up correctly. 914 */ 915 916 void genkillae() 917 { 918 flowxx = AE; 919 assert(go.exptop > 1); 920 foreach (b; dfo[]) 921 { 922 assert(b); 923 vec_clear(b.Bgen); 924 vec_clear(b.Bkill); 925 if (b.Belem) 926 accumaecp(b.Bgen,b.Bkill,b.Belem); 927 else if (b.BC == BCasm) 928 { 929 vec_set(b.Bkill); // KILL everything 930 vec_clear(b.Bgen); // GEN nothing 931 } 932 } 933 } 934 935 /************************************ 936 * Allocate and compute KILL and GEN vectors for a elem. 937 */ 938 939 private void aecpelem(vec_t *pgen,vec_t *pkill, elem *n) 940 { 941 *pgen = vec_calloc(go.exptop); 942 *pkill = vec_calloc(go.exptop); 943 if (n) 944 { 945 if (flowxx == VBE) 946 accumvbe(*pgen,*pkill,n); 947 else 948 accumaecp(*pgen,*pkill,n); 949 } 950 } 951 952 /************************************* 953 * Accumulate GEN and KILL sets for AEs and CPs for this elem. 954 */ 955 956 private __gshared 957 { 958 vec_t GEN; // use static copies to save on parameter passing 959 vec_t KILL; 960 } 961 962 private void accumaecp(vec_t g,vec_t k,elem *n) 963 { vec_t GENsave,KILLsave; 964 965 assert(g && k); 966 GENsave = GEN; 967 KILLsave = KILL; 968 GEN = g; 969 KILL = k; 970 accumaecpx(n); 971 GEN = GENsave; 972 KILL = KILLsave; 973 } 974 975 private void accumaecpx(elem *n) 976 { 977 elem *t; 978 979 assert(n); 980 elem_debug(n); 981 const op = n.Eoper; 982 983 switch (op) 984 { 985 case OPvar: 986 case OPconst: 987 case OPrelconst: 988 if ((flowxx == AE) && n.Eexp) 989 { uint b; 990 debug assert(go.expnod[n.Eexp] == n); 991 b = n.Eexp; 992 vec_setclear(b,GEN,KILL); 993 } 994 return; 995 996 case OPcolon: 997 case OPcolon2: 998 { vec_t Gl,Kl,Gr,Kr; 999 1000 aecpelem(&Gl,&Kl,n.EV.E1); 1001 aecpelem(&Gr,&Kr,n.EV.E2); 1002 1003 /* KILL |= Kl | Kr */ 1004 /* GEN =((GEN - Kl) | Gl) & */ 1005 /* ((GEN - Kr) | Gr) */ 1006 1007 vec_orass(KILL,Kl); 1008 vec_orass(KILL,Kr); 1009 1010 vec_sub(Kl,GEN,Kl); 1011 vec_sub(Kr,GEN,Kr); 1012 vec_orass(Kl,Gl); 1013 vec_orass(Kr,Gr); 1014 vec_and(GEN,Kl,Kr); 1015 1016 vec_free(Gl); 1017 vec_free(Gr); 1018 vec_free(Kl); 1019 vec_free(Kr); 1020 break; 1021 } 1022 1023 case OPandand: 1024 case OPoror: 1025 { vec_t Gr,Kr; 1026 1027 accumaecpx(n.EV.E1); 1028 aecpelem(&Gr,&Kr,n.EV.E2); 1029 1030 if (el_returns(n.EV.E2)) 1031 { 1032 // KILL |= Kr 1033 // GEN &= (GEN - Kr) | Gr 1034 1035 vec_orass(KILL,Kr); 1036 vec_sub(Kr,GEN,Kr); 1037 vec_orass(Kr,Gr); 1038 vec_andass(GEN,Kr); 1039 } 1040 1041 vec_free(Gr); 1042 vec_free(Kr); 1043 break; 1044 } 1045 1046 case OPddtor: 1047 case OPasm: 1048 assert(!n.Eexp); // no ASM available expressions 1049 vec_set(KILL); // KILL everything 1050 vec_clear(GEN); // GEN nothing 1051 return; 1052 1053 case OPeq: 1054 case OPstreq: 1055 accumaecpx(n.EV.E2); 1056 goto case OPnegass; 1057 1058 case OPnegass: 1059 accumaecpx(n.EV.E1); 1060 t = n.EV.E1; 1061 break; 1062 1063 case OPvp_fp: 1064 case OPcvp_fp: // if vptr access 1065 if ((flowxx == AE) && n.Eexp) 1066 vec_orass(KILL,go.vptrkill); // kill all other vptr accesses 1067 break; 1068 1069 case OPprefetch: 1070 accumaecpx(n.EV.E1); // don't check E2 1071 break; 1072 1073 default: 1074 if (OTunary(op)) 1075 { 1076 case OPind: // most common unary operator 1077 accumaecpx(n.EV.E1); 1078 debug assert(!OTassign(op)); 1079 } 1080 else if (OTbinary(op)) 1081 { 1082 if (OTrtol(op) && ERTOL(n)) 1083 { 1084 accumaecpx(n.EV.E2); 1085 accumaecpx(n.EV.E1); 1086 } 1087 else 1088 { 1089 accumaecpx(n.EV.E1); 1090 accumaecpx(n.EV.E2); 1091 } 1092 if (OTassign(op)) // if assignment operator 1093 t = n.EV.E1; 1094 } 1095 break; 1096 } 1097 1098 1099 /* Do copy propagation stuff first */ 1100 1101 if (flowxx == CP) 1102 { 1103 if (!OTdef(op)) /* if not def elem */ 1104 return; 1105 if (!Eunambig(n)) /* if ambiguous def elem */ 1106 { 1107 vec_orass(KILL,go.defkill); 1108 vec_subass(GEN,go.defkill); 1109 } 1110 else /* unambiguous def elem */ 1111 { 1112 assert(t.Eoper == OPvar); 1113 Symbol* s = t.EV.Vsym; // ptr to var being def'd 1114 foreach (uint i; 1 .. go.exptop) // for each ae elem 1115 { 1116 elem *e = go.expnod[i]; 1117 1118 /* If it could be changed by the definition, */ 1119 /* set bit in KILL. */ 1120 1121 if (e.EV.E1.EV.Vsym == s || e.EV.E2.EV.Vsym == s) 1122 vec_setclear(i,KILL,GEN); 1123 } 1124 } 1125 1126 /* GEN CP elems */ 1127 if (n.Eexp) 1128 { 1129 const uint b = n.Eexp; 1130 vec_setclear(b,GEN,KILL); 1131 } 1132 1133 return; 1134 } 1135 1136 /* Else Available Expression stuff */ 1137 1138 if (n.Eexp) 1139 { 1140 const uint b = n.Eexp; // add elem to GEN 1141 assert(go.expnod[b] == n); 1142 vec_setclear(b,GEN,KILL); 1143 } 1144 else if (OTdef(op)) /* else if definition elem */ 1145 { 1146 if (!Eunambig(n)) /* if ambiguous def elem */ 1147 { 1148 vec_orass(KILL,go.defkill); 1149 vec_subass(GEN,go.defkill); 1150 if (OTcalldef(op)) 1151 { 1152 vec_orass(KILL,go.vptrkill); 1153 vec_subass(GEN,go.vptrkill); 1154 } 1155 } 1156 else /* unambiguous def elem */ 1157 { 1158 assert(t.Eoper == OPvar); 1159 Symbol* s = t.EV.Vsym; // idx of var being def'd 1160 if (!(s.Sflags & SFLunambig)) 1161 { 1162 vec_orass(KILL,go.starkill); /* kill all 'starred' refs */ 1163 vec_subass(GEN,go.starkill); 1164 } 1165 foreach (uint i; 1 .. go.exptop) // for each ae elem 1166 { 1167 elem *e = go.expnod[i]; 1168 const int eop = e.Eoper; 1169 1170 /* If it could be changed by the definition, */ 1171 /* set bit in KILL. */ 1172 if (eop == OPvar) 1173 { 1174 if (e.EV.Vsym != s) 1175 continue; 1176 } 1177 else if (OTunary(eop)) 1178 { 1179 if (!vec_testbit(e.EV.E1.Eexp,KILL)) 1180 continue; 1181 } 1182 else if (OTbinary(eop)) 1183 { 1184 if (!vec_testbit(e.EV.E1.Eexp,KILL) && 1185 !vec_testbit(e.EV.E2.Eexp,KILL)) 1186 continue; 1187 } 1188 else 1189 continue; 1190 1191 vec_setclear(i,KILL,GEN); 1192 } 1193 } 1194 1195 /* GEN the lvalue of an assignment operator */ 1196 if (OTassign(op) && !OTpost(op) && t.Eexp) 1197 { 1198 uint b = t.Eexp; 1199 1200 vec_setclear(b,GEN,KILL); 1201 } 1202 } 1203 } 1204 1205 /************************* LIVE VARIABLES **********************/ 1206 1207 /********************************* 1208 * Do live variable analysis (LVs). 1209 * A variable is 'live' at some point if there is a 1210 * subsequent use of it before a redefinition. 1211 * Binlv = the set of variables live at the beginning of B. 1212 * Boutlv = the set of variables live at the end of B. 1213 * Bgen = set of variables used before any definition in B. 1214 * Bkill = set of variables unambiguously defined before 1215 * any use in B. 1216 * Note that Bgen & Bkill = 0. 1217 */ 1218 1219 void flowlv() 1220 { 1221 lvgenkill(); /* compute Bgen and Bkill for LVs. */ 1222 //assert(globsym.length); /* should be at least some symbols */ 1223 1224 /* Create a vector of all the variables that are live on exit */ 1225 /* from the function. */ 1226 1227 vec_t livexit = vec_calloc(globsym.length); 1228 foreach (i; 0 .. globsym.length) 1229 { 1230 if (globsym[i].Sflags & SFLlivexit) 1231 vec_setbit(i,livexit); 1232 } 1233 1234 /* The transfer equation is: */ 1235 /* Bin = (Bout - Bkill) | Bgen */ 1236 /* Bout = union of Bin of all successors to B. */ 1237 /* Using Ullman's algorithm: */ 1238 1239 foreach (b; dfo[]) 1240 { 1241 vec_copy(b.Binlv, b.Bgen); // Binlv = Bgen 1242 } 1243 1244 vec_t tmp = vec_calloc(globsym.length); 1245 uint cnt = 0; 1246 bool anychng; 1247 do 1248 { 1249 anychng = false; 1250 1251 /* For each block B in reverse DFO order */ 1252 foreach_reverse (b; dfo[]) 1253 { 1254 /* Bout = union of Bins of all successors to B. */ 1255 bool first = true; 1256 foreach (bl; ListRange(b.Bsucc)) 1257 { 1258 const inlv = list_block(bl).Binlv; 1259 if (first) 1260 vec_copy(b.Boutlv, inlv); 1261 else 1262 vec_orass(b.Boutlv, inlv); 1263 first = false; 1264 } 1265 1266 if (first) /* no successors, Boutlv = livexit */ 1267 { //assert(b.BC==BCret||b.BC==BCretexp||b.BC==BCexit); 1268 vec_copy(b.Boutlv,livexit); 1269 } 1270 1271 /* Bin = (Bout - Bkill) | Bgen */ 1272 vec_sub(tmp,b.Boutlv,b.Bkill); 1273 vec_orass(tmp,b.Bgen); 1274 if (!anychng) 1275 anychng = !vec_equal(tmp,b.Binlv); 1276 vec_copy(b.Binlv,tmp); 1277 } 1278 cnt++; 1279 assert(cnt < 50); 1280 } while (anychng); 1281 1282 vec_free(tmp); 1283 vec_free(livexit); 1284 1285 static if (0) 1286 { 1287 printf("Live variables\n"); 1288 foreach (i, b; dfo[]) 1289 { 1290 printf("B%d IN\t", cast(int)i); 1291 vec_println(b.Binlv); 1292 printf("B%d GEN\t", cast(int)i); 1293 vec_println(b.Bgen); 1294 printf(" KILL\t"); 1295 vec_println(b.Bkill); 1296 printf(" OUT\t"); 1297 vec_println(b.Boutlv); 1298 } 1299 } 1300 } 1301 1302 /*********************************** 1303 * Compute Bgen and Bkill for LVs. 1304 * Allocate Binlv and Boutlv vectors. 1305 */ 1306 1307 private void lvgenkill() 1308 { 1309 /* Compute ambigsym, a vector of all variables that could be */ 1310 /* referenced by a *e or a call. */ 1311 1312 assert(ambigsym == null); 1313 ambigsym = vec_calloc(globsym.length); 1314 foreach (i; 0 .. globsym.length) 1315 if (!(globsym[i].Sflags & SFLunambig)) 1316 vec_setbit(i,ambigsym); 1317 1318 foreach (b; dfo[]) 1319 { 1320 vec_free(b.Bgen); 1321 vec_free(b.Bkill); 1322 lvelem(&(b.Bgen),&(b.Bkill),b.Belem); 1323 if (b.BC == BCasm) 1324 { 1325 vec_set(b.Bgen); 1326 vec_clear(b.Bkill); 1327 } 1328 1329 vec_free(b.Binlv); 1330 vec_free(b.Boutlv); 1331 b.Binlv = vec_calloc(globsym.length); 1332 b.Boutlv = vec_calloc(globsym.length); 1333 } 1334 1335 vec_free(ambigsym); /* dump any existing one */ 1336 ambigsym = null; 1337 } 1338 1339 /***************************** 1340 * Allocate and compute KILL and GEN for live variables. 1341 */ 1342 1343 private void lvelem(vec_t *pgen,vec_t *pkill,elem *n) 1344 { 1345 *pgen = vec_calloc(globsym.length); 1346 *pkill = vec_calloc(globsym.length); 1347 if (n && globsym.length) 1348 accumlv(*pgen,*pkill,n); 1349 } 1350 1351 /********************************************** 1352 * Accumulate GEN and KILL sets for LVs for this elem. 1353 */ 1354 1355 private void accumlv(vec_t GEN,vec_t KILL,elem *n) 1356 { 1357 assert(GEN && KILL && n); 1358 1359 while (1) 1360 { 1361 elem_debug(n); 1362 const op = n.Eoper; 1363 switch (op) 1364 { 1365 case OPvar: 1366 if (symbol_isintab(n.EV.Vsym)) 1367 { 1368 const si = n.EV.Vsym.Ssymnum; 1369 1370 assert(cast(uint)si < globsym.length); 1371 if (!vec_testbit(si,KILL)) // if not in KILL 1372 vec_setbit(si,GEN); // put in GEN 1373 } 1374 break; 1375 1376 case OPcolon: 1377 case OPcolon2: 1378 { 1379 vec_t Gl,Kl,Gr,Kr; 1380 lvelem(&Gl,&Kl,n.EV.E1); 1381 lvelem(&Gr,&Kr,n.EV.E2); 1382 1383 /* GEN |= (Gl | Gr) - KILL */ 1384 /* KILL |= (Kl & Kr) - GEN */ 1385 1386 vec_orass(Gl,Gr); 1387 vec_subass(Gl,KILL); 1388 vec_orass(GEN,Gl); 1389 vec_andass(Kl,Kr); 1390 vec_subass(Kl,GEN); 1391 vec_orass(KILL,Kl); 1392 1393 vec_free(Gl); 1394 vec_free(Gr); 1395 vec_free(Kl); 1396 vec_free(Kr); 1397 break; 1398 } 1399 1400 case OPandand: 1401 case OPoror: 1402 { 1403 vec_t Gr,Kr; 1404 accumlv(GEN,KILL,n.EV.E1); 1405 lvelem(&Gr,&Kr,n.EV.E2); 1406 1407 /* GEN |= Gr - KILL */ 1408 /* KILL |= 0 */ 1409 1410 vec_subass(Gr,KILL); 1411 vec_orass(GEN,Gr); 1412 1413 vec_free(Gr); 1414 vec_free(Kr); 1415 break; 1416 } 1417 1418 case OPasm: 1419 vec_set(GEN); /* GEN everything not already KILLed */ 1420 vec_subass(GEN,KILL); 1421 break; 1422 1423 case OPcall: 1424 case OPcallns: 1425 case OPstrcpy: 1426 case OPmemcpy: 1427 case OPmemset: 1428 debug assert(OTrtol(op)); 1429 accumlv(GEN,KILL,n.EV.E2); 1430 accumlv(GEN,KILL,n.EV.E1); 1431 goto L1; 1432 1433 case OPstrcat: 1434 debug assert(!OTrtol(op)); 1435 accumlv(GEN,KILL,n.EV.E1); 1436 accumlv(GEN,KILL,n.EV.E2); 1437 L1: 1438 vec_orass(GEN,ambigsym); 1439 vec_subass(GEN,KILL); 1440 break; 1441 1442 case OPeq: 1443 case OPstreq: 1444 { 1445 /* Avoid GENing the lvalue of an = */ 1446 accumlv(GEN,KILL,n.EV.E2); 1447 elem *t = n.EV.E1; 1448 if (t.Eoper != OPvar) 1449 accumlv(GEN,KILL,t.EV.E1); 1450 else /* unambiguous assignment */ 1451 { 1452 Symbol* s = t.EV.Vsym; 1453 symbol_debug(s); 1454 1455 uint tsz = tysize(t.Ety); 1456 if (op == OPstreq) 1457 tsz = cast(uint)type_size(n.ET); 1458 1459 /* if not GENed already, KILL it */ 1460 if (symbol_isintab(s) && 1461 !vec_testbit(s.Ssymnum,GEN) && 1462 t.EV.Voffset == 0 && 1463 tsz == type_size(s.Stype) 1464 ) 1465 { 1466 // printf("%s\n", s.Sident); 1467 assert(cast(uint)s.Ssymnum < globsym.length); 1468 vec_setbit(s.Ssymnum,KILL); 1469 } 1470 } 1471 break; 1472 } 1473 1474 case OPbt: // much like OPind 1475 accumlv(GEN,KILL,n.EV.E1); 1476 accumlv(GEN,KILL,n.EV.E2); 1477 vec_orass(GEN,ambigsym); 1478 vec_subass(GEN,KILL); 1479 break; 1480 1481 case OPind: 1482 case OPucall: 1483 case OPucallns: 1484 case OPstrlen: 1485 accumlv(GEN,KILL,n.EV.E1); 1486 1487 /* If it was a *p elem, set bits in GEN for all symbols */ 1488 /* it could have referenced, but only if bits in KILL */ 1489 /* are not already set. */ 1490 1491 vec_orass(GEN,ambigsym); 1492 vec_subass(GEN,KILL); 1493 break; 1494 1495 default: 1496 if (OTunary(op)) 1497 { 1498 n = n.EV.E1; 1499 continue; 1500 } 1501 else if (OTrtol(op) && ERTOL(n)) 1502 { 1503 accumlv(GEN,KILL,n.EV.E2); 1504 1505 /* Note that lvalues of op=,i++,i-- elems */ 1506 /* are GENed. */ 1507 n = n.EV.E1; 1508 continue; 1509 } 1510 else if (OTbinary(op)) 1511 { 1512 accumlv(GEN,KILL,n.EV.E1); 1513 n = n.EV.E2; 1514 continue; 1515 } 1516 break; 1517 } 1518 break; 1519 } 1520 } 1521 1522 /********************* VERY BUSY EXPRESSIONS ********************/ 1523 1524 /********************************************** 1525 * Compute very busy expressions(VBEs). 1526 * That is,expressions that are evaluated along 1527 * separate paths. 1528 * Bin = the set of VBEs at the beginning of B. 1529 * Bout = the set of VBEs at the end of B. 1530 * Bgen = set of expressions X+Y such that X+Y is 1531 * evaluated before any def of X or Y. 1532 * Bkill = set of expressions X+Y such that X or Y could 1533 * be defined before X+Y is computed. 1534 * Note that gen and kill are mutually exclusive. 1535 */ 1536 1537 void flowvbe() 1538 { 1539 flowxx = VBE; 1540 aecpgenkill(go, VBE); // compute Bgen and Bkill for VBEs 1541 if (go.exptop <= 1) /* if no candidates for VBEs */ 1542 return; 1543 1544 /*foreach (uint i; 0 .. go.exptop) 1545 printf("go.expnod[%d] = 0x%x\n",i,go.expnod[i]);*/ 1546 1547 /* The transfer equation is: */ 1548 /* Bout = & Bin(all successors S of B) */ 1549 /* Bin =(Bout - Bkill) | Bgen */ 1550 /* Using Ullman's algorithm: */ 1551 1552 /*printf("defkill = "); vec_println(go.defkill); 1553 printf("starkill = "); vec_println(go.starkill);*/ 1554 1555 foreach (b; dfo[]) 1556 { 1557 /*printf("block %p\n",b); 1558 printf("Bgen = "); vec_println(b.Bgen); 1559 printf("Bkill = "); vec_println(b.Bkill);*/ 1560 1561 if (b.BC == BCret || b.BC == BCretexp || b.BC == BCexit) 1562 vec_clear(b.Bout); 1563 else 1564 vec_set(b.Bout); 1565 1566 /* Bin = (Bout - Bkill) | Bgen */ 1567 vec_sub(b.Bin,b.Bout,b.Bkill); 1568 vec_orass(b.Bin,b.Bgen); 1569 } 1570 1571 vec_t tmp = vec_calloc(go.exptop); 1572 bool anychng; 1573 do 1574 { 1575 anychng = false; 1576 1577 /* for all blocks except return blocks in reverse dfo order */ 1578 foreach_reverse (b; dfo[]) 1579 { 1580 if (b.BC == BCret || b.BC == BCretexp || b.BC == BCexit) 1581 continue; 1582 1583 /* Bout = & of Bin of all successors */ 1584 bool first = true; 1585 foreach (bl; ListRange(b.Bsucc)) 1586 { 1587 const vin = list_block(bl).Bin; 1588 if (first) 1589 vec_copy(b.Bout, vin); 1590 else 1591 vec_andass(b.Bout, vin); 1592 1593 first = false; 1594 } 1595 1596 assert(!first); // must have successors 1597 1598 /* Bin = (Bout - Bkill) | Bgen */ 1599 vec_sub(tmp,b.Bout,b.Bkill); 1600 vec_orass(tmp,b.Bgen); 1601 if (!anychng) 1602 anychng = !vec_equal(tmp,b.Bin); 1603 vec_copy(b.Bin,tmp); 1604 } 1605 } while (anychng); /* while any changes occurred to any Bin */ 1606 vec_free(tmp); 1607 } 1608 1609 /************************************* 1610 * Accumulate GEN and KILL sets for VBEs for this elem. 1611 */ 1612 1613 private void accumvbe(vec_t GEN,vec_t KILL,elem *n) 1614 { 1615 elem *t; 1616 1617 assert(GEN && KILL && n); 1618 const op = n.Eoper; 1619 1620 switch (op) 1621 { 1622 case OPcolon: 1623 case OPcolon2: 1624 { 1625 vec_t Gl,Gr,Kl,Kr; 1626 1627 aecpelem(&Gl,&Kl,n.EV.E1); 1628 aecpelem(&Gr,&Kr,n.EV.E2); 1629 1630 /* GEN |=((Gr - Kl) | (Gl - Kr)) - KILL */ 1631 vec_subass(Gr,Kl); 1632 vec_subass(Gl,Kr); 1633 vec_orass(Gr,Gl); 1634 vec_subass(Gr,KILL); 1635 vec_orass(GEN,Gr); 1636 1637 /* KILL |=(Kl | Kr) - GEN */ 1638 vec_orass(Kl,Kr); 1639 vec_subass(Kl,GEN); 1640 vec_orass(KILL,Kl); 1641 1642 vec_free(Gl); 1643 vec_free(Kl); 1644 vec_free(Gr); 1645 vec_free(Kr); 1646 break; 1647 } 1648 1649 case OPandand: 1650 case OPoror: 1651 accumvbe(GEN,KILL,n.EV.E1); 1652 /* WARNING: just so happens that it works this way. */ 1653 /* Be careful about (b+c)||(b+c) being VBEs, only the */ 1654 /* first should be GENed. Doing things this way instead */ 1655 /* of (GEN |= Gr - KILL) and (KILL |= Kr - GEN) will */ 1656 /* ensure this. */ 1657 accumvbe(GEN,KILL,n.EV.E2); 1658 break; 1659 1660 case OPnegass: 1661 t = n.EV.E1; 1662 if (t.Eoper != OPvar) 1663 { 1664 accumvbe(GEN,KILL,t.EV.E1); 1665 if (OTbinary(t.Eoper)) 1666 accumvbe(GEN,KILL,t.EV.E2); 1667 } 1668 break; 1669 1670 case OPcall: 1671 case OPcallns: 1672 accumvbe(GEN,KILL,n.EV.E2); 1673 goto case OPucall; 1674 1675 case OPucall: 1676 case OPucallns: 1677 t = n.EV.E1; 1678 // Do not VBE indirect function calls 1679 if (t.Eoper == OPind) 1680 t = t.EV.E1; 1681 accumvbe(GEN,KILL,t); 1682 break; 1683 1684 case OPasm: // if the dreaded OPasm elem 1685 vec_set(KILL); // KILL everything 1686 vec_subass(KILL,GEN); // except for GENed stuff 1687 return; 1688 1689 default: 1690 if (OTunary(op)) 1691 { 1692 t = n.EV.E1; 1693 accumvbe(GEN,KILL,t); 1694 } 1695 else if (ERTOL(n)) 1696 { 1697 accumvbe(GEN,KILL,n.EV.E2); 1698 t = n.EV.E1; 1699 // do not GEN the lvalue of an assignment op 1700 if (OTassign(op)) 1701 { 1702 t = n.EV.E1; 1703 if (t.Eoper != OPvar) 1704 { 1705 accumvbe(GEN,KILL,t.EV.E1); 1706 if (OTbinary(t.Eoper)) 1707 accumvbe(GEN,KILL,t.EV.E2); 1708 } 1709 } 1710 else 1711 accumvbe(GEN,KILL,t); 1712 } 1713 else if (OTbinary(op)) 1714 { 1715 /* do not GEN the lvalue of an assignment op */ 1716 if (OTassign(op)) 1717 { 1718 t = n.EV.E1; 1719 if (t.Eoper != OPvar) 1720 { 1721 accumvbe(GEN,KILL,t.EV.E1); 1722 if (OTbinary(t.Eoper)) 1723 accumvbe(GEN,KILL,t.EV.E2); 1724 } 1725 } 1726 else 1727 accumvbe(GEN,KILL,n.EV.E1); 1728 accumvbe(GEN,KILL,n.EV.E2); 1729 } 1730 break; 1731 } 1732 1733 if (n.Eexp) /* if a vbe elem */ 1734 { 1735 const int ne = n.Eexp; 1736 1737 assert(go.expnod[ne] == n); 1738 if (!vec_testbit(ne,KILL)) /* if not already KILLed */ 1739 { 1740 /* GEN this expression only if it hasn't */ 1741 /* already been GENed in this block. */ 1742 /* (Don't GEN common subexpressions.) */ 1743 if (vec_testbit(ne,GEN)) 1744 vec_clearbit(ne,GEN); 1745 else 1746 { 1747 vec_setbit(ne,GEN); /* GEN this expression */ 1748 /* GEN all identical expressions */ 1749 /* (operators only, as there is no point */ 1750 /* to hoisting out variables and constants) */ 1751 if (!OTleaf(op)) 1752 { 1753 foreach (uint i; 1 .. go.exptop) 1754 { 1755 if (op == go.expnod[i].Eoper && 1756 i != ne && 1757 el_match(n,go.expnod[i])) 1758 { 1759 vec_setbit(i,GEN); 1760 assert(!vec_testbit(i,KILL)); 1761 } 1762 } 1763 } 1764 } 1765 } 1766 if (op == OPvp_fp || op == OPcvp_fp) 1767 { 1768 vec_orass(KILL,go.vptrkill); /* KILL all vptr accesses */ 1769 vec_subass(KILL,GEN); /* except for GENed stuff */ 1770 } 1771 } 1772 else if (OTdef(op)) /* if definition elem */ 1773 { 1774 if (!Eunambig(n)) /* if ambiguous definition */ 1775 { 1776 vec_orass(KILL,go.defkill); 1777 if (OTcalldef(op)) 1778 vec_orass(KILL,go.vptrkill); 1779 } 1780 else /* unambiguous definition */ 1781 { 1782 assert(t.Eoper == OPvar); 1783 Symbol* s = t.EV.Vsym; // ptr to var being def'd 1784 if (!(s.Sflags & SFLunambig)) 1785 vec_orass(KILL,go.starkill);/* kill all 'starred' refs */ 1786 foreach (uint i; 1 .. go.exptop) // for each vbe elem 1787 { 1788 elem *e = go.expnod[i]; 1789 uint eop = e.Eoper; 1790 1791 /* If it could be changed by the definition, */ 1792 /* set bit in KILL. */ 1793 if (eop == OPvar) 1794 { 1795 if (e.EV.Vsym != s) 1796 continue; 1797 } 1798 else if (OTbinary(eop)) 1799 { 1800 if (!vec_testbit(e.EV.E1.Eexp,KILL) && 1801 !vec_testbit(e.EV.E2.Eexp,KILL)) 1802 continue; 1803 } 1804 else if (OTunary(eop)) 1805 { 1806 if (!vec_testbit(e.EV.E1.Eexp,KILL)) 1807 continue; 1808 } 1809 else /* OPconst or OPrelconst or OPstring */ 1810 continue; 1811 1812 vec_setbit(i,KILL); // KILL it 1813 } /* for */ 1814 } /* if */ 1815 vec_subass(KILL,GEN); 1816 } /* if */ 1817 } 1818 1819 }