1: // Copyright (C) 1993-1998 by Symantec
  2: // Copyright (C) 2000-2009 by Digital Mars
  3: // All Rights Reserved
  4: // http://www.digitalmars.com
  5: // Written by Walter Bright
  6: /*
  7:  * This source file is made available for personal use
  8:  * only. The license is in /dmd/src/dmd/backendlicense.txt
  9:  * or /dm/src/dmd/backendlicense.txt
 10:  * For any other uses, please contact Digital Mars.
 11:  */
 12: 
 13: #if !DEMO && !SPP
 14: 
 15: #include        <stdio.h>
 16: #include        <stdlib.h>
 17: #include        <time.h>
 18: 
 19: #if __sun&&__SVR4
 20: #include        <alloca.h>
 21: #elif _MSC_VER
 22: #include        <malloc.h>
 23: #endif
 24: 
 25: #include        "cc.h"
 26: #include        "global.h"
 27: #include        "el.h"
 28: #include        "go.h"
 29: #include        "type.h"
 30: #include        "oper.h"
 31: 
 32: static char __file__[] = __FILE__;      /* for tassert.h                */
 33: #include        "tassert.h"
 34: 
 35: typedef struct loc_t
 36: {
 37:     elem *e;
 38:     int flags;
 39: #       define LFvolatile       1       // contains volatile refs or defs
 40: #       define LFambigref       2       // references ambiguous data
 41: #       define LFambigdef       4       // defines ambiguous data
 42: #       define LFsymref         8       // reference to symbol s
 43: #       define LFsymdef         0x10    // definition of symbol s
 44: #       define LFunambigref     0x20    // references unambiguous data other than s
 45: #       define LFunambigdef     0x40    // defines unambiguous data other than s
 46: #if TX86
 47: #       define LFinp            0x80    // input from I/O port
 48: #       define LFoutp           0x100   // output to I/O port
 49: #endif
 50: #       define LFfloat          0x200   // sets float flags and/or depends on
 51:                                         // floating point settings
 52: } loc_t;
 53: 
 54: static loc_t *loctab;
 55: static unsigned locmax;
 56: static unsigned loctop;
 57: 
 58: STATIC void local_exp(elem *e,int goal);
 59: STATIC int  local_chkrem(elem *e,elem *eu);
 60: STATIC void local_ins(elem *e);
 61: STATIC void local_rem(unsigned u);
 62: STATIC int  local_getflags(elem *e,symbol *s);
 63: STATIC void local_remove(int flags);
 64: STATIC void local_ambigref(void);
 65: STATIC void local_ambigdef(void);
 66: STATIC void local_symref(symbol *s);
 67: STATIC void local_symdef(symbol *s);
 68: 
 69: #if !TX86
 70: static  bool    fcall_seen = FALSE;
 71: #endif
 72: 
 73: ///////////////////////////////
 74: // This optimization attempts to replace sequences like:
 75: //      x = func();
 76: //      y = 3;
 77: //      z = x + 5;
 78: // with:
 79: //      y = 3;
 80: //      z = (x = func()) + 5;
 81: // In other words, we attempt to localize expressions by moving them
 82: // as near as we can to where they are used. This should minimize
 83: // temporary generation and register usage.
 84: 
 85: void localize()
 86: {   block *b;
 87: 
 88:     cmes("localize()\n");
 89: 
 90:     // Table should not get any larger than the symbol table
 91:     locmax = globsym.symmax;
 92:     loctab = (loc_t *) alloca(locmax * sizeof(*loctab));
warning C6255: _alloca indicates failure by raising a stack overflow exception. Consider using _malloca instead
93: 94: for (b = startblock; b; b = b->Bnext) /* for each block */ 95: { 96: loctop = 0; // start over for each block 97: if (b->Belem && 98: /* Overly broad way to account for the case: 99: * try 100: * { i++; 101: * foo(); // throws exception 102: * i++; // shouldn't combine previous i++ with this one 103: * } 104: */ 105: !b->Btry) 106: { 107: local_exp(b->Belem,0); 108: } 109: } 110: } 111: 112: ////////////////////////////////////// 113: // Input: 114: // goal !=0 if we want the result of the expression 115: // 116: 117: STATIC void local_exp(elem *e,int goal) 118: { symbol *s; 119: unsigned u; 120: elem *e1; 121: int op1; 122: 123: Loop: 124: elem_debug(e); 125: int op = e->Eoper; 126: switch (op) 127: { case OPcomma: 128: local_exp(e->E1,0); 129: e = e->E2; 130: goto Loop; 131: 132: case OPandand: 133: case OPoror: 134: local_exp(e->E1,1); 135: loctop = 0; // we can do better than this, fix later 136: break; 137: 138: case OPcolon: 139: case OPcolon2: 140: loctop = 0; // we can do better than this, fix later 141: break; 142: 143: case OPinfo: 144: if (e->E1->Eoper == OPmark) 145: { loctop = 0; 146: e = e->E2; 147: goto Loop; 148: } 149: goto case_bin; 150: 151: case OPdtor: 152: case OPctor: 153: case OPdctor: 154: loctop = 0; // don't move expressions across ctor/dtor 155: break; // boundaries, it would goof up EH cleanup 156: 157: case OPddtor: 158: loctop = 0; // don't move expressions across ctor/dtor 159: // boundaries, it would goof up EH cleanup 160: local_exp(e->E1,0); 161: loctop = 0; 162: break; 163: 164: case OPeq: 165: case OPstreq: 166: e1 = e->E1; 167: local_exp(e->E2,1); 168: if (e1->Eoper == OPvar) 169: { s = e1->EV.sp.Vsym; 170: if (s->Sflags & SFLunambig) 171: { local_symdef(s); 172: #if TX86 173: if (!goal) 174: #else 175: if (!(goal || fcall_seen)) 176: // do not localize if there is a function call on the rhs 177: #endif 178: local_ins(e); 179: } 180: else 181: local_ambigdef(); 182: } 183: else 184: { 185: assert(!OTleaf(e1->Eoper)); 186: local_exp(e1->E1,1); 187: if (OTbinary(e1->Eoper)) 188: local_exp(e1->E2,1); 189: local_ambigdef(); 190: } 191: #if !TX86 192: e1->Nflags |= (e->E2->Nflags & NFLfcall); 193: #endif 194: break; 195: 196: case OPpostinc: 197: case OPpostdec: 198: case OPaddass: 199: case OPminass: 200: case OPmulass: 201: case OPdivass: 202: case OPmodass: 203: case OPashrass: 204: case OPshrass: 205: case OPshlass: 206: case OPandass: 207: case OPxorass: 208: case OPorass: 209: if (ERTOL(e)) 210: { local_exp(e->E2,1); 211: case OPnegass: 212: e1 = e->E1; 213: op1 = e1->Eoper; 214: if (op1 != OPvar) 215: { 216: local_exp(e1->E1,1); 217: if (OTbinary(op1)) 218: local_exp(e1->E2,1); 219: } 220: else if (loctop && (op == OPaddass || op == OPxorass)) 221: { unsigned u;
warning C6246: Local declaration of 'u' hides declaration of the same name in outer scope. For additional information, see previous declaration at line '119' of 'c:\projects\extern\d\dmd\src\backend\glocal.c': Lines: 119
222: 223: s = e1->EV.sp.Vsym; 224: for (u = 0; u < loctop; u++) 225: { elem *em; 226: 227: em = loctab[u].e; 228: if (em->Eoper == op && 229: em->E1->EV.sp.Vsym == s && 230: tysize(em->Ety) == tysize(e1->Ety) && 231: em->E1->EV.sp.Voffset == e1->EV.sp.Voffset && 232: !el_sideeffect(em->E2) 233: ) 234: { // Change (x += a),(x += b) to 235: // (x + a),(x += a + b) 236: changes++; 237: e->E2 = el_bin(opeqtoop(op),e->E2->Ety,em->E2,e->E2); 238: em->Eoper = opeqtoop(op); 239: em->E2 = el_copytree(em->E2); 240: local_rem(u); 241: #ifdef DEBUG 242: if (debugc) 243: { dbg_printf("Combined equation "); 244: WReqn(e); 245: dbg_printf(";\n"); 246: e = doptelem(e,GOALvalue); 247: } 248: #endif 249: 250: break; 251: } 252: } 253: } 254: } 255: else 256: { 257: e1 = e->E1; 258: op1 = e1->Eoper; 259: if (op1 != OPvar) 260: { 261: local_exp(e1->E1,1); 262: if (OTbinary(op1)) 263: local_exp(e1->E2,1); 264: } 265: if (loctop) 266: { if (op1 == OPvar && 267: ((s = e1->EV.sp.Vsym)->Sflags & SFLunambig)) 268: local_symref(s); 269: else 270: local_ambigref(); 271: } 272: local_exp(e->E2,1); 273: } 274: if (op1 == OPvar && 275: ((s = e1->EV.sp.Vsym)->Sflags & SFLunambig)) 276: { local_symref(s); 277: local_symdef(s); 278: if (op == OPaddass || op == OPxorass) 279: local_ins(e); 280: } 281: else if (loctop) 282: { 283: local_remove(LFambigdef | LFambigref); 284: } 285: break; 286: #if TX86 287: case OPstrlen: 288: #endif 289: case OPind: 290: local_exp(e->E1,1); 291: local_ambigref(); 292: break; 293: 294: case OPnewarray: 295: case OPmultinewarray: 296: local_exp(e->E1,1); 297: local_exp(e->E2,1); 298: goto Lrd; 299: 300: #if TX86 301: case OPstrcmp: 302: case OPmemcmp: 303: case OPbt: 304: case OParray: 305: case OPfield: 306: local_exp(e->E1,1); 307: local_exp(e->E2,1); 308: local_ambigref(); 309: break; 310: 311: case OPstrcpy: 312: case OPmemcpy: 313: case OPstrcat: 314: case OPcall: 315: case OPcallns: 316: local_exp(e->E2,1); 317: case OPstrctor: 318: case OPucall: 319: case OPucallns: 320: local_exp(e->E1,1); 321: goto Lrd; 322: 323: case OPbtc: 324: case OPbtr: 325: case OPbts: 326: local_exp(e->E1,1); 327: local_exp(e->E2,1); 328: goto Lrd; 329: #else 330: case OPcall: 331: case OPcallns: 332: { 333: local_exp(e->E2,1); 334: } 335: case OPstrctor: 336: case OPucall: 337: case OPucallns: 338: fcall_seen = FALSE; 339: local_exp(e->E1,1); 340: 341: e->Nflags |= NFLfcall; 342: fcall_seen = TRUE; 343: 344: #endif 345: case OPasm: 346: Lrd: 347: local_remove(LFfloat | LFambigref | LFambigdef); 348: break; 349: 350: #if TX86 351: case OPmemset: 352: local_exp(e->E2,1); 353: if (e->E1->Eoper == OPvar) 354: { 355: /* Don't want to rearrange (p = get(); p memset 0;) 356: * as elemxxx() will rearrange it back. 357: */ 358: s = e->E1->EV.sp.Vsym; 359: if (s->Sflags & SFLunambig) 360: local_symref(s); 361: else 362: local_ambigref(); // ambiguous reference 363: } 364: else 365: local_exp(e->E1,1); 366: local_ambigdef(); 367: break; 368: #endif 369: 370: case OPvar: 371: s = e->EV.sp.Vsym; 372: if (loctop) 373: { unsigned u;
warning C6246: Local declaration of 'u' hides declaration of the same name in outer scope. For additional information, see previous declaration at line '119' of 'c:\projects\extern\d\dmd\src\backend\glocal.c': Lines: 119
374: 375: // If potential candidate for replacement 376: if (s->Sflags & SFLunambig) 377: { 378: for (u = 0; u < loctop; u++) 379: { elem *em; 380: 381: em = loctab[u].e; 382: if (em->E1->EV.sp.Vsym == s && 383: (em->Eoper == OPeq || em->Eoper == OPstreq) 384: #if !TX86 385: && !(em->Nflags & NFLfcall) 386: #endif 387: ) 388: { 389: if (tysize(em->Ety) == tysize(e->Ety) && 390: em->E1->EV.sp.Voffset == e->EV.sp.Voffset && 391: (tyfloating(em->Ety) != 0) == (tyfloating(e->Ety) != 0)) 392: { 393: #ifdef DEBUG 394: if (debugc) 395: { dbg_printf("Moved equation "); 396: WReqn(em); 397: dbg_printf(";\n"); 398: } 399: #endif 400: changes++; 401: em->Ety = e->Ety; 402: el_copy(e,em); 403: em->E1 = em->E2 = NULL; 404: em->Eoper = OPconst; 405: } 406: local_rem(u); 407: break; 408: } 409: } 410: local_symref(s); 411: } 412: else 413: local_ambigref(); // ambiguous reference 414: } 415: break; 416: 417: case OPremquo: 418: if (e->E1->Eoper != OPvar) 419: goto case_bin; 420: s = e->E1->EV.sp.Vsym; 421: if (loctop) 422: { 423: if (s->Sflags & SFLunambig) 424: local_symref(s); 425: else 426: local_ambigref(); // ambiguous reference 427: } 428: goal = 1; 429: e = e->E2; 430: goto Loop; 431: 432: default: 433: if (OTcommut(e->Eoper)) 434: { // Since commutative operators may get their leaves 435: // swapped, we eliminate any that may be affected by that. 436: 437: for (u = 0; u < loctop;) 438: { 439: int f1,f2,f; 440: elem *eu; 441: 442: f = loctab[u].flags; 443: eu = loctab[u].e; 444: s = eu->E1->EV.sp.Vsym; 445: f1 = local_getflags(e->E1,s); 446: f2 = local_getflags(e->E2,s); 447: if (f1 & f2 & LFsymref || // if both reference or 448: (f1 | f2) & LFsymdef || // either define 449: f & LFambigref && (f1 | f2) & LFambigdef || 450: f & LFambigdef && (f1 | f2) & (LFambigref | LFambigdef) 451: ) 452: local_rem(u); 453: else if (f & LFunambigdef && local_chkrem(e,eu->E2)) 454: local_rem(u); 455: else 456: u++; 457: } 458: } 459: if (EUNA(e)) 460: { goal = 1; 461: e = e->E1; 462: goto Loop; 463: } 464: case_bin: 465: if (EBIN(e)) 466: { local_exp(e->E1,1); 467: goal = 1; 468: e = e->E2; 469: goto Loop; 470: } 471: break; 472: } // end of switch (e->Eoper) 473: 474: #if !TX86 475: if (EUNA(e)) 476: { 477: e->Nflags |= (e->E1->Nflags & NFLfcall); 478: } 479: 480: if (EBIN(e)) 481: { 482: e->Nflags |= ((e->E1->Nflags | e->E2->Nflags) & NFLfcall); 483: } 484: #endif 485: } 486: 487: /////////////////////////////////// 488: // Examine expression tree eu to see if it defines any variables 489: // that e refs or defs. 490: // Note that e is a binary operator. 491: // Returns: 492: // !=0 if it does 493: 494: STATIC int local_chkrem(elem *e,elem *eu) 495: { int f1,f2; 496: int op; 497: symbol *s; 498: int result = 0; 499: 500: while (1) 501: { elem_debug(eu); 502: op = eu->Eoper; 503: if (OTassign(op) && eu->E1->Eoper == OPvar) 504: { s = eu->E1->EV.sp.Vsym; 505: f1 = local_getflags(e->E1,s); 506: f2 = local_getflags(e->E2,s); 507: if ((f1 | f2) & (LFsymref | LFsymdef)) // if either reference or define 508: { result = 1; 509: break; 510: } 511: } 512: if (OTbinary(op)) 513: { if (local_chkrem(e,eu->E2)) 514: { result = 1; 515: break; 516: } 517: } 518: else if (!OTunary(op)) 519: break; // leaf node 520: eu = eu->E1; 521: } 522: return result; 523: } 524: 525: ////////////////////////////////////// 526: // Add entry e to loctab[] 527: 528: STATIC void local_ins(elem *e) 529: { 530: elem_debug(e); 531: if (e->E1->Eoper == OPvar) 532: { symbol *s; 533: 534: s = e->E1->EV.sp.Vsym; 535: symbol_debug(s); 536: if (s->Sflags & SFLunambig) // if can only be referenced directly 537: { int flags; 538: 539: flags = local_getflags(e->E2,NULL); 540: #if TX86 541: if (!(flags & (LFvolatile | LFinp | LFoutp)) && 542: #else 543: if (!(flags & LFvolatile) && 544: #endif 545: !(e->E1->Ety & mTYvolatile)) 546: { 547: // Add e to the candidate array 548: //dbg_printf("local_ins('%s'), loctop = %d, locmax = %d\n",s->Sident,loctop,locmax); 549: assert(loctop < locmax); 550: loctab[loctop].e = e; 551: loctab[loctop].flags = flags; 552: loctop++; 553: } 554: } 555: } 556: } 557: 558: ////////////////////////////////////// 559: // Remove entry i from loctab[], and then compress the table. 560: // 561: 562: STATIC void local_rem(unsigned u) 563: { 564: //dbg_printf("local_rem(%u)\n",u); 565: assert(u < loctop); 566: if (u + 1 != loctop) 567: { assert(u < loctop); 568: loctab[u] = loctab[loctop - 1]; 569: } 570: loctop--; 571: } 572: 573: ////////////////////////////////////// 574: // Analyze and gather LFxxxx flags about expression e and symbol s. 575: 576: STATIC int local_getflags(elem *e,symbol *s) 577: { int flags; 578: 579: elem_debug(e); 580: if (s) 581: symbol_debug(s); 582: flags = 0;
warning C4390: ';' : empty controlled statement found; is this the intent?
583: while (1) 584: { 585: if (e->Ety & mTYvolatile) 586: flags |= LFvolatile; 587: switch (e->Eoper) 588: { 589: case OPeq: 590: case OPstreq: 591: if (e->E1->Eoper == OPvar) 592: { symbol *s1; 593: 594: s1 = e->E1->EV.sp.Vsym; 595: if (s1->Sflags & SFLunambig) 596: flags |= (s1 == s) ? LFsymdef : LFunambigdef; 597: else 598: flags |= LFambigdef; 599: } 600: else 601: flags |= LFambigdef; 602: goto L1; 603: 604: case OPpostinc: 605: case OPpostdec: 606: case OPaddass: 607: case OPminass: 608: case OPmulass: 609: case OPdivass: 610: case OPmodass: 611: case OPashrass: 612: case OPshrass: 613: case OPshlass: 614: case OPandass: 615: case OPxorass: 616: case OPorass: 617: if (e->E1->Eoper == OPvar) 618: { symbol *s1; 619: 620: s1 = e->E1->EV.sp.Vsym; 621: if (s1->Sflags & SFLunambig) 622: flags |= (s1 == s) ? LFsymdef | LFsymref 623: : LFunambigdef | LFunambigref; 624: else 625: flags |= LFambigdef | LFambigref; 626: } 627: else 628: flags |= LFambigdef | LFambigref; 629: L1: 630: flags |= local_getflags(e->E2,s); 631: e = e->E1; 632: break; 633: 634: case OPucall: 635: case OPucallns: 636: case OPcall: 637: case OPcallns: 638: case OPnewarray: 639: case OPmultinewarray: 640: #if TX86 641: case OPstrcat: 642: case OPstrcpy: 643: case OPmemcpy: 644: case OPbtc: 645: case OPbtr: 646: case OPbts: 647: #endif 648: case OPstrctor: 649: flags |= LFambigref | LFambigdef; 650: break; 651: 652: #if TX86 653: case OPmemset: 654: flags |= LFambigdef; 655: break; 656: #endif 657: 658: case OPvar: 659: if (e->EV.sp.Vsym == s) 660: flags |= LFsymref; 661: else if (!(e->EV.sp.Vsym->Sflags & SFLunambig)) 662: flags |= LFambigref; 663: break; 664: 665: case OPind: 666: case OParray: 667: case OPfield: 668: #if TX86 669: case OPstrlen: 670: case OPstrcmp: 671: case OPmemcmp: 672: case OPbt: 673: #endif 674: flags |= LFambigref; 675: break; 676: 677: #if TX86 678: case OPinp: 679: flags |= LFinp; 680: break; 681: 682: case OPoutp: 683: flags |= LFoutp; 684: break; 685: #endif 686: } 687: if (EUNA(e)) 688: { 689: if (tyfloating(e->Ety)) 690: flags |= LFfloat; 691: e = e->E1; 692: } 693: else if (EBIN(e)) 694: { 695: if (tyfloating(e->Ety)) 696: flags |= LFfloat; 697: flags |= local_getflags(e->E2,s); 698: e = e->E1; 699: } 700: else 701: break; 702: } 703: return flags; 704: } 705: 706: ////////////////////////////////////// 707: // Remove all entries with flags set. 708: // 709: 710: STATIC void local_remove(int flags) 711: { unsigned u; 712: 713: for (u = 0; u < loctop;) 714: { 715: if (loctab[u].flags & flags) 716: local_rem(u); 717: else 718: u++; 719: } 720: } 721: 722: ////////////////////////////////////// 723: // Ambiguous reference. Remove all with ambiguous defs 724: // 725: 726: STATIC void local_ambigref() 727: { unsigned u; 728: 729: for (u = 0; u < loctop;) 730: { 731: if (loctab[u].flags & LFambigdef) 732: local_rem(u); 733: else 734: u++; 735: } 736: } 737: 738: ////////////////////////////////////// 739: // Ambigous definition. Remove all with ambiguous refs. 740: // 741: 742: STATIC void local_ambigdef() 743: { unsigned u; 744: 745: for (u = 0; u < loctop;) 746: { 747: if (loctab[u].flags & (LFambigref | LFambigdef)) 748: local_rem(u); 749: else 750: u++; 751: } 752: } 753: 754: ////////////////////////////////////// 755: // Reference to symbol. 756: // Remove any that define that symbol. 757: 758: STATIC void local_symref(symbol *s) 759: { unsigned u; 760: 761: symbol_debug(s); 762: for (u = 0; u < loctop;) 763: { 764: if (local_getflags(loctab[u].e,s) & LFsymdef) 765: local_rem(u); 766: else 767: u++; 768: } 769: } 770: 771: ////////////////////////////////////// 772: // Definition of symbol. 773: // Remove any that reference that symbol. 774: 775: STATIC void local_symdef(symbol *s) 776: { unsigned u; 777: 778: symbol_debug(s); 779: for (u = 0; u < loctop;) 780: { 781: if (local_getflags(loctab[u].e,s) & (LFsymref | LFsymdef)) 782: local_rem(u); 783: else 784: u++; 785: } 786: } 787: 788: #endif 789: