dmd/optimize.c

   1
   2 // Compiler implementation of the D programming language
   3 // Copyright (c) 1999-2007 by Digital Mars
   4 // All Rights Reserved
   5 // written by Walter Bright
   6 // http://www.digitalmars.com
   7 // License for redistribution is by either the Artistic License
   8 // in artistic.txt, or the GNU General Public License in gnu.txt.
   9 // See the included readme.txt for details.
  10
  11 /* NOTE: This file has been patched from the original DMD distribution to
  12    work with the GDC compiler.
  13
  14    Modified by David Friedman, December 2006
  15 */
  16
  17 #include <stdio.h>
  18 #include <ctype.h>
  19 #include <assert.h>
  20 #include <math.h>
  21
  22 #if __DMC__
  23 #include <complex.h>
  24 #endif
  25
  26 #include "lexer.h"
  27 #include "mtype.h"
  28 #include "expression.h"
  29 #include "declaration.h"
  30 #include "aggregate.h"
  31 #include "init.h"
  32
  33
  34 #ifdef IN_GCC
  35 #include "d-gcc-real.h"
  36
  37 /* %% fix? */
  38 extern "C" bool real_isnan (const real_t *);
  39 #endif
  40
  41 static real_t zero;     // work around DMC bug for now
  42
  43
  44 /*************************************
  45  * If expression is a variable with a const initializer,
  46  * return that initializer.
  47  */
  48
  49 Expression *fromConstInitializer(Expression *e1)
  50 {
  51     //printf("fromConstInitializer(%s)\n", e1->toChars());
  52     if (e1->op == TOKvar)
  53     {   VarExp *ve = (VarExp *)e1;
  54         VarDeclaration *v = ve->var->isVarDeclaration();
  55         if (v && v->isConst() && v->init)
  56         {   Expression *ei = v->init->toExpression();
  57             if (ei && ei->type)
  58                 e1 = ei;
  59         }
  60     }
  61     return e1;
  62 }
  63
  64
  65 Expression *Expression::optimize(int result)
  66 {
  67     //printf("Expression::optimize(result = x%x) %s\n", result, toChars());
  68     return this;
  69 }
  70
  71 Expression *VarExp::optimize(int result)
  72 {
  73     if (result & WANTinterpret)
  74     {
  75         return fromConstInitializer(this);
  76     }
  77     return this;
  78 }
  79
  80 Expression *TupleExp::optimize(int result)
  81 {
  82     for (size_t i = 0; i < exps->dim; i++)
  83     {   Expression *e = (Expression *)exps->data[i];
  84
  85         e = e->optimize(WANTvalue | (result & WANTinterpret));
  86         exps->data[i] = (void *)e;
  87     }
  88     return this;
  89 }
  90
  91 Expression *ArrayLiteralExp::optimize(int result)
  92 {
  93     if (elements)
  94     {
  95         for (size_t i = 0; i < elements->dim; i++)
  96         {   Expression *e = (Expression *)elements->data[i];
  97
  98             e = e->optimize(WANTvalue | (result & WANTinterpret));
  99             elements->data[i] = (void *)e;
 100         }
 101     }
 102     return this;
 103 }
 104
 105 Expression *AssocArrayLiteralExp::optimize(int result)
 106 {
 107     assert(keys->dim == values->dim);
 108     for (size_t i = 0; i < keys->dim; i++)
 109     {   Expression *e = (Expression *)keys->data[i];
 110
 111         e = e->optimize(WANTvalue | (result & WANTinterpret));
 112         keys->data[i] = (void *)e;
 113
 114         e = (Expression *)values->data[i];
 115         e = e->optimize(WANTvalue | (result & WANTinterpret));
 116         values->data[i] = (void *)e;
 117     }
 118     return this;
 119 }
 120
 121 Expression *StructLiteralExp::optimize(int result)
 122 {
 123     if (elements)
 124     {
 125         for (size_t i = 0; i < elements->dim; i++)
 126         {   Expression *e = (Expression *)elements->data[i];
 127             if (!e)
 128                 continue;
 129             e = e->optimize(WANTvalue | (result & WANTinterpret));
 130             elements->data[i] = (void *)e;
 131         }
 132     }
 133     return this;
 134 }
 135
 136 Expression *TypeExp::optimize(int result)
 137 {
 138     return this;
 139 }
 140
 141 Expression *UnaExp::optimize(int result)
 142 {
 143     e1 = e1->optimize(result);
 144     return this;
 145 }
 146
 147 Expression *NegExp::optimize(int result)
 148 {   Expression *e;
 149
 150     e1 = e1->optimize(result);
 151     if (e1->isConst() == 1)
 152     {
 153         e = Neg(type, e1);
 154     }
 155     else
 156         e = this;
 157     return e;
 158 }
 159
 160 Expression *ComExp::optimize(int result)
 161 {   Expression *e;
 162
 163     e1 = e1->optimize(result);
 164     if (e1->isConst() == 1)
 165     {
 166         e = Com(type, e1);
 167     }
 168     else
 169         e = this;
 170     return e;
 171 }
 172
 173 Expression *NotExp::optimize(int result)
 174 {   Expression *e;
 175
 176     e1 = e1->optimize(result);
 177     if (e1->isConst() == 1)
 178     {
 179         e = Not(type, e1);
 180     }
 181     else
 182         e = this;
 183     return e;
 184 }
 185
 186 Expression *BoolExp::optimize(int result)
 187 {   Expression *e;
 188
 189     e1 = e1->optimize(result);
 190     if (e1->isConst() == 1)
 191     {
 192         e = Bool(type, e1);
 193     }
 194     else
 195         e = this;
 196     return e;
 197 }
 198
 199 Expression *AddrExp::optimize(int result)
 200 {   Expression *e;
 201
 202     //printf("AddrExp::optimize(result = %d) %s\n", result, toChars());
 203     e1 = e1->optimize(result);
 204     // Convert &*ex to ex
 205     if (e1->op == TOKstar)
 206     {   Expression *ex;
 207
 208         ex = ((PtrExp *)e1)->e1;
 209         if (type->equals(ex->type))
 210             e = ex;
 211         else
 212         {
 213             e = ex->copy();
 214             e->type = type;
 215         }
 216         return e;
 217     }
 218     if (e1->op == TOKvar)
 219     {   VarExp *ve = (VarExp *)e1;
 220         if (!ve->var->isOut() && !ve->var->isRef() &&
 221             !ve->var->isImportedSymbol())
 222         {
 223             e = new SymOffExp(loc, ve->var, 0);
 224             e->type = type;
 225             return e;
 226         }
 227     }
 228     if (e1->op == TOKindex)
 229     {   // Convert &array[n] to &array+n
 230         IndexExp *ae = (IndexExp *)e1;
 231
 232         if (ae->e2->op == TOKint64 && ae->e1->op == TOKvar)
 233         {
 234             integer_t index = ae->e2->toInteger();
 235             VarExp *ve = (VarExp *)ae->e1;
 236             if (ve->type->ty == Tsarray && ve->type->next->ty != Tbit
 237                 && !ve->var->isImportedSymbol())
 238             {
 239                 TypeSArray *ts = (TypeSArray *)ve->type;
 240                 integer_t dim = ts->dim->toInteger();
 241                 if (index < 0 || index >= dim)
 242                     error("array index %"PRIdMAX" is out of bounds [0..%"PRIdMAX"]", index, dim);
 243                 e = new SymOffExp(loc, ve->var, index * ts->next->size());
 244                 e->type = type;
 245                 return e;
 246             }
 247         }
 248     }
 249     return this;
 250 }
 251
 252 Expression *PtrExp::optimize(int result)
 253 {
 254     //printf("PtrExp::optimize(result = x%x) %s\n", result, toChars());
 255     e1 = e1->optimize(result);
 256     // Convert *&ex to ex
 257     if (e1->op == TOKaddress)
 258     {   Expression *e;
 259         Expression *ex;
 260
 261         ex = ((AddrExp *)e1)->e1;
 262         if (type->equals(ex->type))
 263             e = ex;
 264         else
 265         {
 266 #ifndef IN_GCC
 267             e = ex->copy();
 268             e->type = type;
 269 #else
 270             // Stuffing types does not always work in GCC
 271             return this;
 272 #endif
 273         }
 274         return e;
 275     }
 276     // Constant fold *(&structliteral + offset)
 277     if (e1->op == TOKadd)
 278     {
 279         Expression *e;
 280         e = Ptr(type, e1);
 281         if (e != EXP_CANT_INTERPRET)
 282             return e;
 283     }
 284
 285     return this;
 286 }
 287
 288 Expression *CallExp::optimize(int result)
 289 {   Expression *e = this;
 290
 291     e1 = e1->optimize(result);
 292     if (e1->op == TOKvar && result & WANTinterpret)
 293     {
 294         FuncDeclaration *fd = ((VarExp *)e1)->var->isFuncDeclaration();
 295         if (fd)
 296         {
 297             Expression *eresult = fd->interpret(NULL, arguments);
 298             if (eresult && eresult != EXP_VOID_INTERPRET)
 299                 e = eresult;
 300             else if (result & WANTinterpret)
 301                 error("cannot evaluate %s at compile time", toChars());
 302         }
 303     }
 304     return e;
 305 }
 306
 307
 308 Expression *CastExp::optimize(int result)
 309 {
 310     //printf("CastExp::optimize(result = %d) %s\n", result, toChars());
 311     //printf("from %s to %s\n", type->toChars(), to->toChars());
 312     //printf("from %s\n", type->toChars());
 313     //printf("type = %p\n", type);
 314     assert(type);
 315     enum TOK op1 = e1->op;
 316
 317     e1 = e1->optimize(result);
 318     if (result & WANTinterpret)
 319         e1 = fromConstInitializer(e1);
 320
 321     if ((e1->op == TOKstring || e1->op == TOKarrayliteral) &&
 322         (type->ty == Tpointer || type->ty == Tarray) &&
 323         type->next->equals(e1->type->next)
 324        )
 325     {
 326         e1->type = type;
 327         return e1;
 328     }
 329     /* The first test here is to prevent infinite loops
 330      */
 331     if (op1 != TOKarrayliteral && e1->op == TOKarrayliteral)
 332         return e1->castTo(NULL, to);
 333     if (e1->op == TOKnull &&
 334         (type->ty == Tpointer || type->ty == Tclass))
 335     {
 336         e1->type = type;
 337         return e1;
 338     }
 339
 340     if (result & WANTflags && type->ty == Tclass && e1->type->ty == Tclass)
 341     {
 342         // See if we can remove an unnecessary cast
 343         ClassDeclaration *cdfrom;
 344         ClassDeclaration *cdto;
 345         target_ptrdiff_t offset;
 346
 347         cdfrom = e1->type->isClassHandle();
 348         cdto   = type->isClassHandle();
 349         if (cdto->isBaseOf(cdfrom, &offset) && offset == 0)
 350         {
 351             e1->type = type;
 352             return e1;
 353         }
 354     }
 355
 356     Expression *e;
 357
 358     if (e1->isConst())
 359     {
 360         if (e1->op == TOKsymoff)
 361         {
 362             if (type->size() == e1->type->size() &&
 363                 type->toBasetype()->ty != Tsarray)
 364             {
 365                 e1->type = type;
 366                 return e1;
 367             }
 368             return this;
 369         }
 370         if (to->toBasetype()->ty == Tvoid)
 371             e = this;
 372         else
 373             e = Cast(type, to, e1);
 374     }
 375     else
 376         e = this;
 377     return e;
 378 }
 379
 380 Expression *BinExp::optimize(int result)
 381 {
 382     //printf("BinExp::optimize(result = %d) %s\n", result, toChars());
 383     e1 = e1->optimize(result);
 384     e2 = e2->optimize(result);
 385     if (op == TOKshlass || op == TOKshrass || op == TOKushrass)
 386     {
 387         if (e2->isConst() == 1)
 388         {
 389             integer_t i2 = e2->toInteger();
 390             d_uns64 sz = e1->type->size() * 8;
 391             if (i2 < 0 || i2 > sz)
 392             {   error("shift assign by %jd is outside the range 0..%zu", i2, sz);
 393                 e2 = new IntegerExp(0);
 394             }
 395         }
 396     }
 397     return this;
 398 }
 399
 400 Expression *AddExp::optimize(int result)
 401 {   Expression *e;
 402
 403     //printf("AddExp::optimize(%s)\n", toChars());
 404     e1 = e1->optimize(result);
 405     e2 = e2->optimize(result);
 406     if (e1->isConst() && e2->isConst())
 407     {
 408         if (e1->op == TOKsymoff && e2->op == TOKsymoff)
 409             return this;
 410         e = Add(type, e1, e2);
 411     }
 412     else
 413         e = this;
 414     return e;
 415 }
 416
 417 Expression *MinExp::optimize(int result)
 418 {   Expression *e;
 419
 420     e1 = e1->optimize(result);
 421     e2 = e2->optimize(result);
 422     if (e1->isConst() && e2->isConst())
 423     {
 424         if (e2->op == TOKsymoff)
 425             return this;
 426         e = Min(type, e1, e2);
 427     }
 428     else
 429         e = this;
 430     return e;
 431 }
 432
 433 Expression *MulExp::optimize(int result)
 434 {   Expression *e;
 435
 436     //printf("MulExp::optimize(result = %d) %s\n", result, toChars());
 437     e1 = e1->optimize(result);
 438     e2 = e2->optimize(result);
 439     if (e1->isConst() == 1 && e2->isConst() == 1)
 440     {
 441         e = Mul(type, e1, e2);
 442     }
 443     else
 444         e = this;
 445     return e;
 446 }
 447
 448 Expression *DivExp::optimize(int result)
 449 {   Expression *e;
 450
 451     //printf("DivExp::optimize(%s)\n", toChars());
 452     e1 = e1->optimize(result);
 453     e2 = e2->optimize(result);
 454     if (e1->isConst() == 1 && e2->isConst() == 1)
 455     {
 456         e = Div(type, e1, e2);
 457     }
 458     else
 459         e = this;
 460     return e;
 461 }
 462
 463 Expression *ModExp::optimize(int result)
 464 {   Expression *e;
 465
 466     e1 = e1->optimize(result);
 467     e2 = e2->optimize(result);
 468     if (e1->isConst() == 1 && e2->isConst() == 1)
 469     {
 470         e = Mod(type, e1, e2);
 471     }
 472     else
 473         e = this;
 474     return e;
 475 }
 476
 477 Expression *shift_optimize(int result, BinExp *e, Expression *(*shift)(Type *, Expression *, Expression *))
 478 {   Expression *ex = e;
 479
 480     e->e1 = e->e1->optimize(result);
 481     e->e2 = e->e2->optimize(result);
 482     if (e->e2->isConst() == 1)
 483     {
 484         integer_t i2 = e->e2->toInteger();
 485         target_size_t sz = e->e1->type->size() * 8;
 486         if (i2 < 0 || i2 > sz)
 487         {   error("shift left by %"PRIdMAX" exceeds %"PRIuTSIZE, i2, sz);
 488             e->e2 = new IntegerExp(0);
 489         }
 490         if (e->e1->isConst() == 1)
 491             ex = (*shift)(e->type, e->e1, e->e2);
 492     }
 493     return ex;
 494 }
 495
 496 Expression *ShlExp::optimize(int result)
 497 {
 498     //printf("ShlExp::optimize(result = %d) %s\n", result, toChars());
 499     return shift_optimize(result, this, Shl);
 500 }
 501
 502 Expression *ShrExp::optimize(int result)
 503 {
 504     //printf("ShrExp::optimize(result = %d) %s\n", result, toChars());
 505     return shift_optimize(result, this, Shr);
 506 }
 507
 508 Expression *UshrExp::optimize(int result)
 509 {
 510     //printf("UshrExp::optimize(result = %d) %s\n", result, toChars());
 511     return shift_optimize(result, this, Ushr);
 512 }
 513
 514 Expression *AndExp::optimize(int result)
 515 {   Expression *e;
 516
 517     e1 = e1->optimize(result);
 518     e2 = e2->optimize(result);
 519     if (e1->isConst() == 1 && e2->isConst() == 1)
 520         e = And(type, e1, e2);
 521     else
 522         e = this;
 523     return e;
 524 }
 525
 526 Expression *OrExp::optimize(int result)
 527 {   Expression *e;
 528
 529     e1 = e1->optimize(result);
 530     e2 = e2->optimize(result);
 531     if (e1->isConst() == 1 && e2->isConst() == 1)
 532         e = Or(type, e1, e2);
 533     else
 534         e = this;
 535     return e;
 536 }
 537
 538 Expression *XorExp::optimize(int result)
 539 {   Expression *e;
 540
 541     e1 = e1->optimize(result);
 542     e2 = e2->optimize(result);
 543     if (e1->isConst() == 1 && e2->isConst() == 1)
 544         e = Xor(type, e1, e2);
 545     else
 546         e = this;
 547     return e;
 548 }
 549
 550 Expression *CommaExp::optimize(int result)
 551 {   Expression *e;
 552
 553     //printf("CommaExp::optimize(result = %d) %s\n", result, toChars());
 554     e1 = e1->optimize(result & WANTinterpret);
 555     e2 = e2->optimize(result);
 556     if (!e1 || e1->op == TOKint64 || e1->op == TOKfloat64 || !e1->checkSideEffect(2))
 557     {
 558         e = e2;
 559         if (e)
 560             e->type = type;
 561     }
 562     else
 563         e = this;
 564     //printf("-CommaExp::optimize(result = %d) %s\n", result, e->toChars());
 565     return e;
 566 }
 567
 568 Expression *ArrayLengthExp::optimize(int result)
 569 {   Expression *e;
 570
 571     //printf("ArrayLengthExp::optimize(result = %d) %s\n", result, toChars());
 572     e1 = e1->optimize(WANTvalue | (result & WANTinterpret));
 573     e = this;
 574     if (e1->op == TOKstring || e1->op == TOKarrayliteral || e1->op == TOKassocarrayliteral)
 575     {
 576         e = ArrayLength(type, e1);
 577     }
 578     return e;
 579 }
 580
 581 Expression *EqualExp::optimize(int result)
 582 {   Expression *e;
 583
 584     //printf("EqualExp::optimize(result = %x) %s\n", result, toChars());
 585     e1 = e1->optimize(WANTvalue | (result & WANTinterpret));
 586     e2 = e2->optimize(WANTvalue | (result & WANTinterpret));
 587     e = this;
 588
 589     Expression *e1 = fromConstInitializer(this->e1);
 590     Expression *e2 = fromConstInitializer(this->e2);
 591
 592     e = Equal(op, type, e1, e2);
 593     if (e == EXP_CANT_INTERPRET)
 594         e = this;
 595     return e;
 596 }
 597
 598 Expression *IdentityExp::optimize(int result)
 599 {   Expression *e;
 600
 601     //printf("IdentityExp::optimize(result = %d) %s\n", result, toChars());
 602     e1 = e1->optimize(WANTvalue | (result & WANTinterpret));
 603     e2 = e2->optimize(WANTvalue | (result & WANTinterpret));
 604     e = this;
 605     if (this->e1->isConst() && this->e2->isConst())
 606     {
 607         e = Identity(op, type, this->e1, this->e2);
 608     }
 609     return e;
 610 }
 611
 612 Expression *IndexExp::optimize(int result)
 613 {   Expression *e;
 614
 615     //printf("IndexExp::optimize(result = %d) %s\n", result, toChars());
 616     Expression *e1 = this->e1->optimize(WANTvalue | (result & WANTinterpret));
 617     if (result & WANTinterpret)
 618         e1 = fromConstInitializer(e1);
 619     e2 = e2->optimize(WANTvalue | (result & WANTinterpret));
 620     e = Index(type, e1, e2);
 621     if (e == EXP_CANT_INTERPRET)
 622         e = this;
 623     return e;
 624 }
 625
 626 Expression *SliceExp::optimize(int result)
 627 {   Expression *e;
 628
 629     //printf("SliceExp::optimize(result = %d) %s\n", result, toChars());
 630     e = this;
 631     e1 = e1->optimize(WANTvalue | (result & WANTinterpret));
 632     if (!lwr)
 633     {   if (e1->op == TOKstring)
 634         {   // Convert slice of string literal into dynamic array
 635             Type *t = e1->type->toBasetype();
 636             if (t->next)
 637                 e = e1->castTo(NULL, t->next->arrayOf());
 638         }
 639         return e;
 640     }
 641     if (result & WANTinterpret)
 642         e1 = fromConstInitializer(e1);
 643     lwr = lwr->optimize(WANTvalue | (result & WANTinterpret));
 644     upr = upr->optimize(WANTvalue | (result & WANTinterpret));
 645     e = Slice(type, e1, lwr, upr);
 646     if (e == EXP_CANT_INTERPRET)
 647         e = this;
 648     return e;
 649 }
 650
 651 Expression *AndAndExp::optimize(int result)
 652 {   Expression *e;
 653
 654     //printf("AndAndExp::optimize(%d) %s\n", result, toChars());
 655     e1 = e1->optimize(WANTflags | (result & WANTinterpret));
 656     e = this;
 657     if (e1->isBool(FALSE))
 658     {
 659         e = new CommaExp(loc, e1, new IntegerExp(loc, 0, type));
 660         e->type = type;
 661         e = e->optimize(result);
 662     }
 663     else
 664     {
 665         e2 = e2->optimize(WANTflags | (result & WANTinterpret));
 666         if (result && e2->type->toBasetype()->ty == Tvoid && !global.errors)
 667             error("void has no value");
 668         if (e1->isConst())
 669         {
 670             if (e2->isConst())
 671             {   int n1 = e1->isBool(1);
 672                 int n2 = e2->isBool(1);
 673
 674                 e = new IntegerExp(loc, n1 && n2, type);
 675             }
 676             else if (e1->isBool(TRUE))
 677                 e = new BoolExp(loc, e2, type);
 678         }
 679     }
 680     return e;
 681 }
 682
 683 Expression *OrOrExp::optimize(int result)
 684 {   Expression *e;
 685
 686     e1 = e1->optimize(WANTflags | (result & WANTinterpret));
 687     e = this;
 688     if (e1->isBool(TRUE))
 689     {   // Replace with (e1, 1)
 690         e = new CommaExp(loc, e1, new IntegerExp(loc, 1, type));
 691         e->type = type;
 692         e = e->optimize(result);
 693     }
 694     else
 695     {
 696         e2 = e2->optimize(WANTflags | (result & WANTinterpret));
 697         if (result && e2->type->toBasetype()->ty == Tvoid && !global.errors)
 698             error("void has no value");
 699         if (e1->isConst())
 700         {
 701             if (e2->isConst())
 702             {   int n1 = e1->isBool(1);
 703                 int n2 = e2->isBool(1);
 704
 705                 e = new IntegerExp(loc, n1 || n2, type);
 706             }
 707             else if (e1->isBool(FALSE))
 708                 e = new BoolExp(loc, e2, type);
 709         }
 710     }
 711     return e;
 712 }
 713
 714 Expression *CmpExp::optimize(int result)
 715 {   Expression *e;
 716
 717     //printf("CmpExp::optimize() %s\n", toChars());
 718     e1 = e1->optimize(result);
 719     e2 = e2->optimize(result);
 720     if (e1->isConst() == 1 && e2->isConst() == 1)
 721     {
 722         e = Cmp(op, type, this->e1, this->e2);
 723     }
 724     else
 725         e = this;
 726     return e;
 727 }
 728
 729 Expression *CatExp::optimize(int result)
 730 {   Expression *e;
 731
 732     //printf("CatExp::optimize(%d) %s\n", result, toChars());
 733     e1 = e1->optimize(result);
 734     e2 = e2->optimize(result);
 735     e = Cat(type, e1, e2);
 736     if (e == EXP_CANT_INTERPRET)
 737         e = this;
 738     return e;
 739 }
 740
 741
 742 Expression *CondExp::optimize(int result)
 743 {   Expression *e;
 744
 745     econd = econd->optimize(WANTflags | (result & WANTinterpret));
 746     if (econd->isBool(TRUE))
 747         e = e1->optimize(result);
 748     else if (econd->isBool(FALSE))
 749         e = e2->optimize(result);
 750     else
 751     {   e1 = e1->optimize(result);
 752         e2 = e2->optimize(result);
 753         e = this;
 754     }
 755     return e;
 756 }
 757
 758