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