1 /** 2 * Compiler implementation of the 3 * $(LINK2 http://www.dlang.org, D programming language). 4 * 5 * Compute common subexpressions for non-optimized builds. 6 * 7 * Copyright: Copyright (C) 1985-1995 by Symantec 8 * Copyright (C) 2000-2020 by The D Language Foundation, All Rights Reserved 9 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 10 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 11 * Source: https://github.com/dlang/dmd/blob/master/src/dmd/backend/cgcs.d 12 * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/backend/cgcs.d 13 */ 14 15 module dmd.backend.cgcs; 16 17 version (SPP) 18 { 19 } 20 else 21 { 22 23 import core.stdc.stdio; 24 import core.stdc.stdlib; 25 26 import dmd.backend.cc; 27 import dmd.backend.cdef; 28 import dmd.backend.code; 29 import dmd.backend.el; 30 import dmd.backend.global; 31 import dmd.backend.oper; 32 import dmd.backend.ty; 33 import dmd.backend.type; 34 35 import dmd.backend.barray; 36 import dmd.backend.dlist; 37 import dmd.backend.dvec; 38 39 40 nothrow: 41 42 /******************************* 43 * Eliminate common subexpressions across extended basic blocks. 44 * String together as many blocks as we can. 45 */ 46 47 public extern (C++) void comsubs() 48 { 49 //static int xx; 50 //printf("comsubs() %d\n", ++xx); 51 //debugx = (xx == 37); 52 53 debug if (debugx) printf("comsubs(%p)\n",startblock); 54 55 // No longer do we just compute Bcount. We now eliminate unreachable 56 // blocks. 57 block_compbcount(); // eliminate unreachable blocks 58 59 version (SCPP) 60 { 61 if (errcnt) 62 return; 63 } 64 65 if (!csvec) 66 { 67 csvec = vec_calloc(CSVECDIM); 68 } 69 70 block* bln; 71 for (block* bl = startblock; bl; bl = bln) 72 { 73 bln = bl.Bnext; 74 if (!bl.Belem) 75 continue; /* if no expression or no parents */ 76 77 // Count up n, the number of blocks in this extended basic block (EBB) 78 int n = 1; // always at least one block in EBB 79 auto blc = bl; 80 while (bln && list_nitems(bln.Bpred) == 1 && 81 ((blc.BC == BCiftrue && 82 blc.nthSucc(1) == bln) || 83 (blc.BC == BCgoto && blc.nthSucc(0) == bln) 84 ) && 85 bln.BC != BCasm // no CSE's extending across ASM blocks 86 ) 87 { 88 n++; // add block to EBB 89 blc = bln; 90 bln = blc.Bnext; 91 } 92 vec_clear(csvec); 93 hcstab.setLength(0); 94 hcsarray.touchstari = 0; 95 hcsarray.touchfunci[0] = 0; 96 hcsarray.touchfunci[1] = 0; 97 bln = bl; 98 while (n--) // while more blocks in EBB 99 { 100 debug if (debugx) 101 printf("cses for block %p\n",bln); 102 103 if (bln.Belem) 104 ecom(&bln.Belem); // do the tree 105 bln = bln.Bnext; 106 } 107 } 108 109 debug if (debugx) 110 printf("done with comsubs()\n"); 111 } 112 113 /******************************* 114 */ 115 116 public extern (C++) void cgcs_term() 117 { 118 vec_free(csvec); 119 csvec = null; 120 debug debugw && printf("freeing hcstab\n"); 121 //hcstab.dtor(); // cache allocation for next iteration 122 } 123 124 125 /***********************************************************************/ 126 127 private: 128 129 alias hash_t = uint; // for hash values 130 131 /********************************* 132 * Struct for each elem: 133 * Helem pointer to elem 134 * Hhash hash value for the elem 135 */ 136 137 struct HCS 138 { 139 elem* Helem; 140 hash_t Hhash; 141 } 142 143 struct HCSArray 144 { 145 uint touchstari; 146 uint[2] touchfunci; 147 } 148 149 __gshared 150 { 151 Barray!HCS hcstab; // array of hcs's 152 HCSArray hcsarray; 153 154 // Use a bit vector for quick check if expression is possibly in hcstab[]. 155 // This results in much faster compiles when hcstab[] gets big. 156 vec_t csvec; // vector of used entries 157 enum CSVECDIM = 16001; //8009 //3001 // dimension of csvec (should be prime) 158 } 159 160 161 /************************* 162 * Eliminate common subexpressions for an element. 163 */ 164 165 void ecom(elem **pe) 166 { 167 auto e = *pe; 168 assert(e); 169 elem_debug(e); 170 debug assert(e.Ecount == 0); 171 //assert(e.Ecomsub == 0); 172 const tym = tybasic(e.Ety); 173 const op = e.Eoper; 174 switch (op) 175 { 176 case OPconst: 177 case OPrelconst: 178 break; 179 180 case OPvar: 181 if (e.EV.Vsym.ty() & mTYshared) 182 return; // don't cache shared variables 183 break; 184 185 case OPstreq: 186 case OPpostinc: 187 case OPpostdec: 188 case OPeq: 189 case OPaddass: 190 case OPminass: 191 case OPmulass: 192 case OPdivass: 193 case OPmodass: 194 case OPshrass: 195 case OPashrass: 196 case OPshlass: 197 case OPandass: 198 case OPxorass: 199 case OPorass: 200 case OPvecsto: 201 /* Reverse order of evaluation for double op=. This is so that */ 202 /* the pushing of the address of the second operand is easier. */ 203 /* However, with the 8087 we don't need the kludge. */ 204 if (op != OPeq && tym == TYdouble && !config.inline8087) 205 { 206 if (!OTleaf(e.EV.E1.Eoper)) 207 ecom(&e.EV.E1.EV.E1); 208 ecom(&e.EV.E2); 209 } 210 else 211 { 212 /* Don't mark the increment of an i++ or i-- as a CSE, if it */ 213 /* can be done with an INC or DEC instruction. */ 214 if (!(OTpost(op) && elemisone(e.EV.E2))) 215 ecom(&e.EV.E2); /* evaluate 2nd operand first */ 216 case OPnegass: 217 if (!OTleaf(e.EV.E1.Eoper)) /* if lvalue is an operator */ 218 { 219 if (e.EV.E1.Eoper != OPind) 220 elem_print(e); 221 assert(e.EV.E1.Eoper == OPind); 222 ecom(&(e.EV.E1.EV.E1)); 223 } 224 } 225 touchlvalue(e.EV.E1); 226 if (!OTpost(op)) /* lvalue of i++ or i-- is not a cse*/ 227 { 228 const hash = cs_comphash(e.EV.E1); 229 vec_setbit(hash % CSVECDIM,csvec); 230 addhcstab(e.EV.E1,hash); // add lvalue to hcstab[] 231 } 232 return; 233 234 case OPbtc: 235 case OPbts: 236 case OPbtr: 237 case OPcmpxchg: 238 ecom(&e.EV.E1); 239 ecom(&e.EV.E2); 240 touchfunc(0); // indirect assignment 241 return; 242 243 case OPandand: 244 case OPoror: 245 { 246 ecom(&e.EV.E1); 247 const lengthSave = hcstab.length; 248 auto hcsarraySave = hcsarray; 249 ecom(&e.EV.E2); 250 hcsarray = hcsarraySave; // no common subs by E2 251 hcstab.setLength(lengthSave); 252 return; /* if comsub then logexp() will */ 253 } 254 255 case OPcond: 256 { 257 ecom(&e.EV.E1); 258 const lengthSave = hcstab.length; 259 auto hcsarraySave = hcsarray; 260 ecom(&e.EV.E2.EV.E1); // left condition 261 hcsarray = hcsarraySave; // no common subs by E2 262 hcstab.setLength(lengthSave); 263 ecom(&e.EV.E2.EV.E2); // right condition 264 hcsarray = hcsarraySave; // no common subs by E2 265 hcstab.setLength(lengthSave); 266 return; // can't be a common sub 267 } 268 269 case OPcall: 270 case OPcallns: 271 ecom(&e.EV.E2); /* eval right first */ 272 goto case OPucall; 273 274 case OPucall: 275 case OPucallns: 276 ecom(&e.EV.E1); 277 touchfunc(1); 278 return; 279 280 case OPstrpar: /* so we don't break logexp() */ 281 case OPinp: /* never CSE the I/O instruction itself */ 282 case OPprefetch: // don't CSE E2 or the instruction 283 ecom(&e.EV.E1); 284 goto case OPasm; 285 286 case OPasm: 287 case OPstrthis: // don't CSE these 288 case OPframeptr: 289 case OPgot: 290 case OPctor: 291 case OPdtor: 292 case OPdctor: 293 case OPmark: 294 return; 295 296 case OPddtor: 297 touchall(); 298 ecom(&e.EV.E1); 299 touchall(); 300 return; 301 302 case OPparam: 303 case OPoutp: 304 ecom(&e.EV.E1); 305 goto case OPinfo; 306 307 case OPinfo: 308 ecom(&e.EV.E2); 309 return; 310 311 case OPcomma: 312 ecom(&e.EV.E1); 313 ecom(&e.EV.E2); 314 return; 315 316 case OPremquo: 317 ecom(&e.EV.E1); 318 ecom(&e.EV.E2); 319 break; 320 321 case OPvp_fp: 322 case OPcvp_fp: 323 ecom(&e.EV.E1); 324 touchaccess(hcstab, e); 325 break; 326 327 case OPind: 328 ecom(&e.EV.E1); 329 /* Generally, CSEing a *(double *) results in worse code */ 330 if (tyfloating(tym)) 331 return; 332 if (tybasic(e.EV.E1.Ety) == TYsharePtr) 333 return; 334 break; 335 336 case OPstrcpy: 337 case OPstrcat: 338 case OPmemcpy: 339 case OPmemset: 340 ecom(&e.EV.E2); 341 goto case OPsetjmp; 342 343 case OPsetjmp: 344 ecom(&e.EV.E1); 345 touchfunc(0); 346 return; 347 348 default: /* other operators */ 349 if (!OTbinary(e.Eoper)) 350 WROP(e.Eoper); 351 assert(OTbinary(e.Eoper)); 352 goto case OPadd; 353 354 case OPadd: 355 case OPmin: 356 case OPmul: 357 case OPdiv: 358 case OPor: 359 case OPxor: 360 case OPand: 361 case OPeqeq: 362 case OPne: 363 case OPscale: 364 case OPyl2x: 365 case OPyl2xp1: 366 ecom(&e.EV.E1); 367 ecom(&e.EV.E2); 368 break; 369 370 case OPstring: 371 case OPaddr: 372 case OPbit: 373 WROP(e.Eoper); 374 elem_print(e); 375 assert(0); /* optelem() should have removed these */ 376 /* NOTREACHED */ 377 378 // Explicitly list all the unary ops for speed 379 case OPnot: case OPcom: case OPneg: case OPuadd: 380 case OPabs: case OPrndtol: case OPrint: 381 case OPpreinc: case OPpredec: 382 case OPbool: case OPstrlen: case OPs16_32: case OPu16_32: 383 case OPs32_d: case OPu32_d: case OPd_s16: case OPs16_d: case OP32_16: 384 case OPf_d: 385 case OPld_d: 386 case OPc_r: case OPc_i: 387 case OPu8_16: case OPs8_16: case OP16_8: 388 case OPu32_64: case OPs32_64: case OP64_32: case OPmsw: 389 case OPu64_128: case OPs64_128: case OP128_64: 390 case OPs64_d: case OPd_u64: case OPu64_d: 391 case OPstrctor: case OPu16_d: case OPd_u16: 392 case OParrow: 393 case OPvoid: 394 case OPbsf: case OPbsr: case OPbswap: case OPpopcnt: case OPvector: 395 case OPld_u64: 396 case OPsqrt: case OPsin: case OPcos: 397 case OPoffset: case OPnp_fp: case OPnp_f16p: case OPf16p_np: 398 case OPvecfill: 399 ecom(&e.EV.E1); 400 break; 401 402 case OPd_ld: 403 return; 404 405 case OPd_f: 406 { 407 const op1 = e.EV.E1.Eoper; 408 if (config.fpxmmregs && 409 (op1 == OPs32_d || 410 I64 && (op1 == OPs64_d || op1 == OPu32_d)) 411 ) 412 ecom(&e.EV.E1.EV.E1); // e and e1 ops are fused (see xmmcnvt()) 413 else 414 ecom(&e.EV.E1); 415 break; 416 } 417 418 case OPd_s32: 419 case OPd_u32: 420 case OPd_s64: 421 if (e.EV.E1.Eoper == OPf_d && config.fpxmmregs) 422 ecom(&e.EV.E1.EV.E1); // e and e1 ops are fused (see xmmcnvt()); 423 else 424 ecom(&e.EV.E1); 425 break; 426 427 case OPhalt: 428 return; 429 } 430 431 /* don't CSE structures or unions or volatile stuff */ 432 if (tym == TYstruct || 433 tym == TYvoid || 434 e.Ety & mTYvolatile) 435 return; 436 if (tyfloating(tym) && config.inline8087) 437 { 438 /* can CSE XMM code, but not x87 439 */ 440 if (!(config.fpxmmregs && tyxmmreg(tym))) 441 return; 442 } 443 444 const hash = cs_comphash(e); /* must be AFTER leaves are done */ 445 446 /* Search for a match in hcstab[]. 447 * Search backwards, as most likely matches will be towards the end 448 * of the list. 449 */ 450 451 debug if (debugx) printf("elem: %p hash: %6d\n",e,hash); 452 int csveci = hash % CSVECDIM; 453 if (vec_testbit(csveci,csvec)) 454 { 455 foreach_reverse (i, ref hcs; hcstab[]) 456 { 457 debug if (debugx) 458 printf("i: %2d Hhash: %6d Helem: %p\n", 459 cast(int) i,hcs.Hhash,hcs.Helem); 460 461 elem* ehash; 462 if (hash == hcs.Hhash && (ehash = hcs.Helem) != null) 463 { 464 /* if elems are the same and we still have room for more */ 465 if (el_match(e,ehash) && ehash.Ecount < 0xFF) 466 { 467 /* Make sure leaves are also common subexpressions 468 * to avoid false matches. 469 */ 470 if (!OTleaf(op)) 471 { 472 if (!e.EV.E1.Ecount) 473 continue; 474 if (OTbinary(op) && !e.EV.E2.Ecount) 475 continue; 476 } 477 ehash.Ecount++; 478 *pe = ehash; 479 480 debug if (debugx) 481 printf("**MATCH** %p with %p\n",e,*pe); 482 483 el_free(e); 484 return; 485 } 486 } 487 } 488 } 489 else 490 vec_setbit(csveci,csvec); 491 addhcstab(e,hash); // add this elem to hcstab[] 492 } 493 494 /************************** 495 * Compute hash function for elem e. 496 */ 497 498 hash_t cs_comphash(const elem *e) 499 { 500 elem_debug(e); 501 const op = e.Eoper; 502 hash_t hash = (e.Ety & (mTYbasic | mTYconst | mTYvolatile)) + (op << 8); 503 if (!OTleaf(op)) 504 { 505 hash += cast(size_t) e.EV.E1; 506 if (OTbinary(op)) 507 hash += cast(size_t) e.EV.E2; 508 } 509 else 510 { 511 hash += e.EV.Vint; 512 if (op == OPvar || op == OPrelconst) 513 hash += cast(size_t) e.EV.Vsym; 514 } 515 return hash; 516 } 517 518 /**************************** 519 * Add an elem to the common subexpression table. 520 */ 521 522 void addhcstab(elem *e, hash_t hash) 523 { 524 hcstab.push(HCS(e, hash)); 525 } 526 527 /*************************** 528 * "touch" the elem. 529 * If it is a pointer, "touch" all the suspects 530 * who could be pointed to. 531 * Eliminate common subs that are indirect loads. 532 */ 533 534 void touchlvalue(elem *e) 535 { 536 if (e.Eoper == OPind) /* if indirect store */ 537 { 538 /* NOTE: Some types of array assignments do not need 539 * to touch all variables. (Like a[5], where a is an 540 * array instead of a pointer.) 541 */ 542 543 touchfunc(0); 544 return; 545 } 546 547 foreach_reverse (ref hcs; hcstab[]) 548 { 549 if (hcs.Helem && 550 hcs.Helem.EV.Vsym == e.EV.Vsym) 551 hcs.Helem = null; 552 } 553 554 if (!(e.Eoper == OPvar || e.Eoper == OPrelconst)) 555 elem_print(e); 556 assert(e.Eoper == OPvar || e.Eoper == OPrelconst); 557 switch (e.EV.Vsym.Sclass) 558 { 559 case SCregpar: 560 case SCregister: 561 case SCpseudo: 562 break; 563 564 case SCauto: 565 case SCparameter: 566 case SCfastpar: 567 case SCshadowreg: 568 case SCbprel: 569 if (e.EV.Vsym.Sflags & SFLunambig) 570 break; 571 goto case SCstatic; 572 573 case SCstatic: 574 case SCextern: 575 case SCglobal: 576 case SClocstat: 577 case SCcomdat: 578 case SCinline: 579 case SCsinline: 580 case SCeinline: 581 case SCcomdef: 582 touchstar(); 583 break; 584 585 default: 586 elem_print(e); 587 symbol_print(e.EV.Vsym); 588 assert(0); 589 } 590 } 591 592 /************************** 593 * "touch" variables that could be changed by a function call or 594 * an indirect assignment. 595 * Eliminate any subexpressions that are "starred" (they need to 596 * be recomputed). 597 * Params: 598 * flag = If 1, then this is a function call. 599 * If 0, then this is an indirect assignment. 600 */ 601 602 void touchfunc(int flag) 603 { 604 605 //printf("touchfunc(%d)\n", flag); 606 HCS *petop = hcstab.ptr + hcstab.length; 607 //pe = &hcstab[0]; printf("pe = %p, petop = %p\n",pe,petop); 608 assert(hcsarray.touchfunci[flag] <= hcstab.length); 609 for (HCS *pe = hcstab.ptr + hcsarray.touchfunci[flag]; pe < petop; pe++) 610 { 611 elem *he = pe.Helem; 612 if (!he) 613 continue; 614 switch (he.Eoper) 615 { 616 case OPvar: 617 if (Symbol_isAffected(*he.EV.Vsym)) 618 { 619 pe.Helem = null; 620 continue; 621 } 622 break; 623 624 case OPind: 625 if (tybasic(he.EV.E1.Ety) == TYimmutPtr) 626 break; 627 goto Ltouch; 628 629 case OPstrlen: 630 case OPstrcmp: 631 case OPmemcmp: 632 case OPbt: 633 goto Ltouch; 634 635 case OPvp_fp: 636 case OPcvp_fp: 637 if (flag == 0) /* function calls destroy vptrfptr's, */ 638 break; /* not indirect assignments */ 639 Ltouch: 640 pe.Helem = null; 641 break; 642 643 default: 644 break; 645 } 646 } 647 hcsarray.touchfunci[flag] = cast(uint)hcstab.length; 648 } 649 650 651 /******************************* 652 * Eliminate all common subexpressions that 653 * do any indirection ("starred" elems). 654 */ 655 656 void touchstar() 657 { 658 foreach (ref hcs; hcstab[hcsarray.touchstari .. $]) 659 { 660 const e = hcs.Helem; 661 if (e && 662 (e.Eoper == OPind && tybasic(e.EV.E1.Ety) != TYimmutPtr || 663 e.Eoper == OPbt) ) 664 hcs.Helem = null; 665 } 666 hcsarray.touchstari = cast(uint)hcstab.length; 667 } 668 669 /******************************* 670 * Eliminate all common subexpressions. 671 */ 672 673 void touchall() 674 { 675 foreach (ref hcs; hcstab[]) 676 { 677 hcs.Helem = null; 678 } 679 hcsarray.touchstari = cast(uint)hcstab.length; 680 hcsarray.touchfunci[0] = cast(uint)hcstab.length; 681 hcsarray.touchfunci[1] = cast(uint)hcstab.length; 682 } 683 684 /***************************************** 685 * Eliminate any common subexpressions that could be modified 686 * if a handle pointer access occurs. 687 */ 688 689 void touchaccess(ref Barray!HCS hcstab, const elem *ev) pure nothrow 690 { 691 const ev1 = ev.EV.E1; 692 foreach (ref hcs; hcstab[]) 693 { 694 const e = hcs.Helem; 695 /* Invalidate any previous handle pointer accesses that */ 696 /* are not accesses of ev. */ 697 if (e && (e.Eoper == OPvp_fp || e.Eoper == OPcvp_fp) && e.EV.E1 != ev1) 698 hcs.Helem = null; 699 } 700 } 701 702 }