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