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