1 2/* Compiler implementation of the D programming language 3 * Copyright (C) 1999-2019 by The D Language Foundation, All Rights Reserved 4 * written by Walter Bright 5 * http://www.digitalmars.com 6 * Distributed under the Boost Software License, Version 1.0 7 * http://www.boost.org/LICENSE_1_0.txt 8 * https://github.com/D-Programming-Language/dmd/blob/master/src/optimize.c 9 */ 10 11#include "root/dsystem.h" 12 13#include "root/checkedint.h" 14#include "lexer.h" 15#include "mtype.h" 16#include "expression.h" 17#include "declaration.h" 18#include "aggregate.h" 19#include "init.h" 20#include "enum.h" 21#include "ctfe.h" 22#include "errors.h" 23 24Expression *semantic(Expression *e, Scope *sc); 25 26/************************************* 27 * If variable has a const initializer, 28 * return that initializer. 29 */ 30 31Expression *expandVar(int result, VarDeclaration *v) 32{ 33 //printf("expandVar(result = %d, v = %p, %s)\n", result, v, v ? v->toChars() : "null"); 34 35 Expression *e = NULL; 36 if (!v) 37 return e; 38 if (!v->originalType && v->semanticRun < PASSsemanticdone) // semantic() not yet run 39 v->semantic(NULL); 40 41 if (v->isConst() || v->isImmutable() || v->storage_class & STCmanifest) 42 { 43 if (!v->type) 44 { 45 return e; 46 } 47 Type *tb = v->type->toBasetype(); 48 if (v->storage_class & STCmanifest || 49 v->type->toBasetype()->isscalar() || 50 ((result & WANTexpand) && (tb->ty != Tsarray && tb->ty != Tstruct)) 51 ) 52 { 53 if (v->_init) 54 { 55 if (v->inuse) 56 { 57 if (v->storage_class & STCmanifest) 58 { 59 v->error("recursive initialization of constant"); 60 goto Lerror; 61 } 62 goto L1; 63 } 64 Expression *ei = v->getConstInitializer(); 65 if (!ei) 66 { 67 if (v->storage_class & STCmanifest) 68 { 69 v->error("enum cannot be initialized with %s", v->_init->toChars()); 70 goto Lerror; 71 } 72 goto L1; 73 } 74 if (ei->op == TOKconstruct || ei->op == TOKblit) 75 { 76 AssignExp *ae = (AssignExp *)ei; 77 ei = ae->e2; 78 if (ei->isConst() == 1) 79 { 80 } 81 else if (ei->op == TOKstring) 82 { 83 // Bugzilla 14459: We should not constfold the string literal 84 // if it's typed as a C string, because the value expansion 85 // will drop the pointer identity. 86 if (!(result & WANTexpand) && ei->type->toBasetype()->ty == Tpointer) 87 goto L1; 88 } 89 else 90 goto L1; 91 92 if (ei->type == v->type) 93 { 94 // const variable initialized with const expression 95 } 96 else if (ei->implicitConvTo(v->type) >= MATCHconst) 97 { 98 // const var initialized with non-const expression 99 ei = ei->implicitCastTo(NULL, v->type); 100 ei = semantic(ei, NULL); 101 } 102 else 103 goto L1; 104 } 105 else if (!(v->storage_class & STCmanifest) && 106 ei->isConst() != 1 && ei->op != TOKstring && 107 ei->op != TOKaddress) 108 { 109 goto L1; 110 } 111 if (!ei->type) 112 { 113 goto L1; 114 } 115 else 116 { 117 // Should remove the copy() operation by 118 // making all mods to expressions copy-on-write 119 e = ei->copy(); 120 } 121 } 122 else 123 { 124 goto L1; 125 } 126 if (e->type != v->type) 127 { 128 e = e->castTo(NULL, v->type); 129 } 130 v->inuse++; 131 e = e->optimize(result); 132 v->inuse--; 133 } 134 } 135L1: 136 //if (e) printf("\te = %p, %s, e->type = %d, %s\n", e, e->toChars(), e->type->ty, e->type->toChars()); 137 return e; 138 139Lerror: 140 return new ErrorExp(); 141} 142 143 144Expression *fromConstInitializer(int result, Expression *e1) 145{ 146 //printf("fromConstInitializer(result = %x, %s)\n", result, e1->toChars()); 147 //static int xx; if (xx++ == 10) assert(0); 148 Expression *e = e1; 149 if (e1->op == TOKvar) 150 { 151 VarExp *ve = (VarExp *)e1; 152 VarDeclaration *v = ve->var->isVarDeclaration(); 153 e = expandVar(result, v); 154 if (e) 155 { 156 // If it is a comma expression involving a declaration, we mustn't 157 // perform a copy -- we'd get two declarations of the same variable. 158 // See bugzilla 4465. 159 if (e->op == TOKcomma && ((CommaExp *)e)->e1->op == TOKdeclaration) 160 e = e1; 161 else 162 163 if (e->type != e1->type && e1->type && e1->type->ty != Tident) 164 { 165 // Type 'paint' operation 166 e = e->copy(); 167 e->type = e1->type; 168 } 169 e->loc = e1->loc; 170 } 171 else 172 { 173 e = e1; 174 } 175 } 176 return e; 177} 178 179Expression *Expression_optimize(Expression *e, int result, bool keepLvalue) 180{ 181 class OptimizeVisitor : public Visitor 182 { 183 public: 184 int result; 185 bool keepLvalue; 186 Expression *ret; 187 188 OptimizeVisitor(int result, bool keepLvalue) 189 : result(result), keepLvalue(keepLvalue) 190 { 191 } 192 193 void error() 194 { 195 ret = new ErrorExp(); 196 } 197 198 bool expOptimize(Expression *&e, int flags, bool keepLvalue = false) 199 { 200 if (!e) 201 return false; 202 Expression *ex = e->optimize(flags, keepLvalue); 203 if (ex->op == TOKerror) 204 { 205 ret = ex; // store error result 206 return true; 207 } 208 else 209 { 210 e = ex; // modify original 211 return false; 212 } 213 } 214 215 bool unaOptimize(UnaExp *e, int flags) 216 { 217 return expOptimize(e->e1, flags); 218 } 219 220 bool binOptimize(BinExp *e, int flags) 221 { 222 expOptimize(e->e1, flags); 223 expOptimize(e->e2, flags); 224 return ret->op == TOKerror; 225 } 226 227 void visit(Expression *) 228 { 229 //printf("Expression::optimize(result = x%x) %s\n", result, e->toChars()); 230 } 231 232 void visit(VarExp *e) 233 { 234 if (keepLvalue) 235 { 236 VarDeclaration *v = e->var->isVarDeclaration(); 237 if (v && !(v->storage_class & STCmanifest)) 238 return; 239 } 240 ret = fromConstInitializer(result, e); 241 } 242 243 void visit(TupleExp *e) 244 { 245 expOptimize(e->e0, WANTvalue); 246 for (size_t i = 0; i < e->exps->dim; i++) 247 { 248 expOptimize((*e->exps)[i], WANTvalue); 249 } 250 } 251 252 void visit(ArrayLiteralExp *e) 253 { 254 if (e->elements) 255 { 256 expOptimize(e->basis, result & WANTexpand); 257 for (size_t i = 0; i < e->elements->dim; i++) 258 { 259 expOptimize((*e->elements)[i], result & WANTexpand); 260 } 261 } 262 } 263 264 void visit(AssocArrayLiteralExp *e) 265 { 266 assert(e->keys->dim == e->values->dim); 267 for (size_t i = 0; i < e->keys->dim; i++) 268 { 269 expOptimize((*e->keys)[i], result & WANTexpand); 270 expOptimize((*e->values)[i], result & WANTexpand); 271 } 272 } 273 274 void visit(StructLiteralExp *e) 275 { 276 if (e->stageflags & stageOptimize) return; 277 int old = e->stageflags; 278 e->stageflags |= stageOptimize; 279 if (e->elements) 280 { 281 for (size_t i = 0; i < e->elements->dim; i++) 282 { 283 expOptimize((*e->elements)[i], result & WANTexpand); 284 } 285 } 286 e->stageflags = old; 287 } 288 289 void visit(UnaExp *e) 290 { 291 //printf("UnaExp::optimize() %s\n", e->toChars()); 292 if (unaOptimize(e, result)) 293 return; 294 } 295 296 void visit(NegExp *e) 297 { 298 if (unaOptimize(e, result)) 299 return; 300 301 if (e->e1->isConst() == 1) 302 { 303 ret = Neg(e->type, e->e1).copy(); 304 } 305 } 306 307 void visit(ComExp *e) 308 { 309 if (unaOptimize(e, result)) 310 return; 311 312 if (e->e1->isConst() == 1) 313 { 314 ret = Com(e->type, e->e1).copy(); 315 } 316 } 317 318 void visit(NotExp *e) 319 { 320 if (unaOptimize(e, result)) 321 return; 322 323 if (e->e1->isConst() == 1) 324 { 325 ret = Not(e->type, e->e1).copy(); 326 } 327 } 328 329 void visit(SymOffExp *e) 330 { 331 assert(e->var); 332 } 333 334 void visit(AddrExp *e) 335 { 336 //printf("AddrExp::optimize(result = %d) %s\n", result, e->toChars()); 337 338 /* Rewrite &(a,b) as (a,&b) 339 */ 340 if (e->e1->op == TOKcomma) 341 { 342 CommaExp *ce = (CommaExp *)e->e1; 343 AddrExp *ae = new AddrExp(e->loc, ce->e2, e->type); 344 ret = new CommaExp(ce->loc, ce->e1, ae); 345 ret->type = e->type; 346 return; 347 } 348 349 // Keep lvalue-ness 350 if (expOptimize(e->e1, result, true)) 351 return; 352 353 // Convert &*ex to ex 354 if (e->e1->op == TOKstar) 355 { 356 Expression *ex = ((PtrExp *)e->e1)->e1; 357 if (e->type->equals(ex->type)) 358 ret = ex; 359 else if (e->type->toBasetype()->equivalent(ex->type->toBasetype())) 360 { 361 ret = ex->copy(); 362 ret->type = e->type; 363 } 364 return; 365 } 366 if (e->e1->op == TOKvar) 367 { 368 VarExp *ve = (VarExp *)e->e1; 369 if (!ve->var->isOut() && !ve->var->isRef() && 370 !ve->var->isImportedSymbol()) 371 { 372 ret = new SymOffExp(e->loc, ve->var, 0, ve->hasOverloads); 373 ret->type = e->type; 374 return; 375 } 376 } 377 if (e->e1->op == TOKindex) 378 { 379 // Convert &array[n] to &array+n 380 IndexExp *ae = (IndexExp *)e->e1; 381 382 if (ae->e2->op == TOKint64 && ae->e1->op == TOKvar) 383 { 384 sinteger_t index = ae->e2->toInteger(); 385 VarExp *ve = (VarExp *)ae->e1; 386 if (ve->type->ty == Tsarray 387 && !ve->var->isImportedSymbol()) 388 { 389 TypeSArray *ts = (TypeSArray *)ve->type; 390 sinteger_t dim = ts->dim->toInteger(); 391 if (index < 0 || index >= dim) 392 { 393 e->error("array index %lld is out of bounds [0..%lld]", index, dim); 394 return error(); 395 } 396 397 bool overflow = false; 398 const d_uns64 offset = mulu(index, ts->nextOf()->size(e->loc), overflow); 399 if (overflow) 400 { 401 e->error("array offset overflow"); 402 return error(); 403 } 404 405 ret = new SymOffExp(e->loc, ve->var, offset); 406 ret->type = e->type; 407 return; 408 } 409 } 410 } 411 } 412 413 void visit(PtrExp *e) 414 { 415 //printf("PtrExp::optimize(result = x%x) %s\n", result, e->toChars()); 416 if (expOptimize(e->e1, result)) 417 return; 418 // Convert *&ex to ex 419 // But only if there is no type punning involved 420 if (e->e1->op == TOKaddress) 421 { 422 Expression *ex = ((AddrExp *)e->e1)->e1; 423 if (e->type->equals(ex->type)) 424 ret = ex; 425 else if (e->type->toBasetype()->equivalent(ex->type->toBasetype())) 426 { 427 ret = ex->copy(); 428 ret->type = e->type; 429 } 430 } 431 if (keepLvalue) 432 return; 433 434 // Constant fold *(&structliteral + offset) 435 if (e->e1->op == TOKadd) 436 { 437 Expression *ex = Ptr(e->type, e->e1).copy(); 438 if (!CTFEExp::isCantExp(ex)) 439 { 440 ret = ex; 441 return; 442 } 443 } 444 445 if (e->e1->op == TOKsymoff) 446 { 447 SymOffExp *se = (SymOffExp *)e->e1; 448 VarDeclaration *v = se->var->isVarDeclaration(); 449 Expression *ex = expandVar(result, v); 450 if (ex && ex->op == TOKstructliteral) 451 { 452 StructLiteralExp *sle = (StructLiteralExp *)ex; 453 ex = sle->getField(e->type, (unsigned)se->offset); 454 if (ex && !CTFEExp::isCantExp(ex)) 455 { 456 ret = ex; 457 return; 458 } 459 } 460 } 461 } 462 463 void visit(DotVarExp *e) 464 { 465 //printf("DotVarExp::optimize(result = x%x) %s\n", result, e->toChars()); 466 if (expOptimize(e->e1, result)) 467 return; 468 if (keepLvalue) 469 return; 470 471 Expression *ex = e->e1; 472 473 if (ex->op == TOKvar) 474 { 475 VarExp *ve = (VarExp *)ex; 476 VarDeclaration *v = ve->var->isVarDeclaration(); 477 ex = expandVar(result, v); 478 } 479 480 if (ex && ex->op == TOKstructliteral) 481 { 482 StructLiteralExp *sle = (StructLiteralExp *)ex; 483 VarDeclaration *vf = e->var->isVarDeclaration(); 484 if (vf && !vf->overlapped) 485 { 486 /* Bugzilla 13021: Prevent optimization if vf has overlapped fields. 487 */ 488 ex = sle->getField(e->type, vf->offset); 489 if (ex && !CTFEExp::isCantExp(ex)) 490 { 491 ret = ex; 492 return; 493 } 494 } 495 } 496 } 497 498 void visit(NewExp *e) 499 { 500 expOptimize(e->thisexp, WANTvalue); 501 502 // Optimize parameters 503 if (e->newargs) 504 { 505 for (size_t i = 0; i < e->newargs->dim; i++) 506 { 507 expOptimize((*e->newargs)[i], WANTvalue); 508 } 509 } 510 511 if (e->arguments) 512 { 513 for (size_t i = 0; i < e->arguments->dim; i++) 514 { 515 expOptimize((*e->arguments)[i], WANTvalue); 516 } 517 } 518 } 519 520 void visit(CallExp *e) 521 { 522 //printf("CallExp::optimize(result = %d) %s\n", result, e->toChars()); 523 524 // Optimize parameters with keeping lvalue-ness 525 if (expOptimize(e->e1, result)) 526 return; 527 if (e->arguments) 528 { 529 Type *t1 = e->e1->type->toBasetype(); 530 if (t1->ty == Tdelegate) t1 = t1->nextOf(); 531 assert(t1->ty == Tfunction); 532 TypeFunction *tf = (TypeFunction *)t1; 533 for (size_t i = 0; i < e->arguments->dim; i++) 534 { 535 Parameter *p = Parameter::getNth(tf->parameters, i); 536 bool keep = p && (p->storageClass & (STCref | STCout)) != 0; 537 expOptimize((*e->arguments)[i], WANTvalue, keep); 538 } 539 } 540 } 541 542 void visit(CastExp *e) 543 { 544 //printf("CastExp::optimize(result = %d) %s\n", result, e->toChars()); 545 //printf("from %s to %s\n", e->type->toChars(), e->to->toChars()); 546 //printf("from %s\n", e->type->toChars()); 547 //printf("e1->type %s\n", e->e1->type->toChars()); 548 //printf("type = %p\n", e->type); 549 assert(e->type); 550 TOK op1 = e->e1->op; 551 552 Expression *e1old = e->e1; 553 if (expOptimize(e->e1, result)) 554 return; 555 e->e1 = fromConstInitializer(result, e->e1); 556 557 if (e->e1 == e1old && 558 e->e1->op == TOKarrayliteral && 559 e->type->toBasetype()->ty == Tpointer && 560 e->e1->type->toBasetype()->ty != Tsarray) 561 { 562 // Casting this will result in the same expression, and 563 // infinite loop because of Expression::implicitCastTo() 564 return; // no change 565 } 566 567 if ((e->e1->op == TOKstring || e->e1->op == TOKarrayliteral) && 568 (e->type->ty == Tpointer || e->type->ty == Tarray)) 569 { 570 const d_uns64 esz = e->type->nextOf()->size(e->loc); 571 const d_uns64 e1sz = e->e1->type->toBasetype()->nextOf()->size(e->e1->loc); 572 if (esz == SIZE_INVALID || e1sz == SIZE_INVALID) 573 return error(); 574 575 if (e1sz == esz) 576 { 577 // Bugzilla 12937: If target type is void array, trying to paint 578 // e->e1 with that type will cause infinite recursive optimization. 579 if (e->type->nextOf()->ty == Tvoid) 580 return; 581 582 ret = e->e1->castTo(NULL, e->type); 583 //printf(" returning1 %s\n", ret->toChars()); 584 return; 585 } 586 } 587 588 if (e->e1->op == TOKstructliteral && 589 e->e1->type->implicitConvTo(e->type) >= MATCHconst) 590 { 591 //printf(" returning2 %s\n", e->e1->toChars()); 592 L1: // Returning e1 with changing its type 593 ret = (e1old == e->e1 ? e->e1->copy() : e->e1); 594 ret->type = e->type; 595 return; 596 } 597 598 /* The first test here is to prevent infinite loops 599 */ 600 if (op1 != TOKarrayliteral && e->e1->op == TOKarrayliteral) 601 { 602 ret = e->e1->castTo(NULL, e->to); 603 return; 604 } 605 if (e->e1->op == TOKnull && 606 (e->type->ty == Tpointer || e->type->ty == Tclass || e->type->ty == Tarray)) 607 { 608 //printf(" returning3 %s\n", e->e1->toChars()); 609 goto L1; 610 } 611 612 if (e->type->ty == Tclass && e->e1->type->ty == Tclass) 613 { 614 // See if we can remove an unnecessary cast 615 ClassDeclaration *cdfrom = e->e1->type->isClassHandle(); 616 ClassDeclaration *cdto = e->type->isClassHandle(); 617 if (cdto == ClassDeclaration::object && !cdfrom->isInterfaceDeclaration()) 618 goto L1; // can always convert a class to Object 619 // Need to determine correct offset before optimizing away the cast. 620 // https://issues.dlang.org/show_bug.cgi?id=16980 621 cdfrom->size(e->loc); 622 assert(cdfrom->sizeok == SIZEOKdone); 623 assert(cdto->sizeok == SIZEOKdone || !cdto->isBaseOf(cdfrom, NULL)); 624 int offset; 625 if (cdto->isBaseOf(cdfrom, &offset) && offset == 0) 626 { 627 //printf(" returning4 %s\n", e->e1->toChars()); 628 goto L1; 629 } 630 } 631 632 // We can convert 'head const' to mutable 633 if (e->to->mutableOf()->constOf()->equals(e->e1->type->mutableOf()->constOf())) 634 { 635 //printf(" returning5 %s\n", e->e1->toChars()); 636 goto L1; 637 } 638 639 if (e->e1->isConst()) 640 { 641 if (e->e1->op == TOKsymoff) 642 { 643 if (e->type->toBasetype()->ty != Tsarray) 644 { 645 const d_uns64 esz = e->type->size(e->loc); 646 const d_uns64 e1sz = e->e1->type->size(e->e1->loc); 647 if (esz == SIZE_INVALID || 648 e1sz == SIZE_INVALID) 649 return error(); 650 651 if (esz == e1sz) 652 goto L1; 653 } 654 return; 655 } 656 if (e->to->toBasetype()->ty != Tvoid) 657 { 658 if (e->e1->type->equals(e->type) && e->type->equals(e->to)) 659 ret = e->e1; 660 else 661 ret = Cast(e->loc, e->type, e->to, e->e1).copy(); 662 } 663 } 664 //printf(" returning6 %s\n", ret->toChars()); 665 } 666 667 void visit(BinExp *e) 668 { 669 //printf("BinExp::optimize(result = %d) %s\n", result, e->toChars()); 670 // don't replace const variable with its initializer in e1 671 bool e2only = (e->op == TOKconstruct || e->op == TOKblit); 672 if (e2only ? expOptimize(e->e2, result) : binOptimize(e, result)) 673 return; 674 675 if (e->op == TOKshlass || e->op == TOKshrass || e->op == TOKushrass) 676 { 677 if (e->e2->isConst() == 1) 678 { 679 sinteger_t i2 = e->e2->toInteger(); 680 d_uns64 sz = e->e1->type->size(e->e1->loc); 681 assert(sz != SIZE_INVALID); 682 sz *= 8; 683 if (i2 < 0 || (d_uns64)i2 >= sz) 684 { 685 e->error("shift assign by %lld is outside the range 0..%llu", i2, (ulonglong)sz - 1); 686 return error(); 687 } 688 } 689 } 690 } 691 692 void visit(AddExp *e) 693 { 694 //printf("AddExp::optimize(%s)\n", e->toChars()); 695 696 if (binOptimize(e, result)) 697 return; 698 699 if (e->e1->isConst() && e->e2->isConst()) 700 { 701 if (e->e1->op == TOKsymoff && e->e2->op == TOKsymoff) 702 return; 703 ret = Add(e->loc, e->type, e->e1, e->e2).copy(); 704 } 705 } 706 707 void visit(MinExp *e) 708 { 709 if (binOptimize(e, result)) 710 return; 711 712 if (e->e1->isConst() && e->e2->isConst()) 713 { 714 if (e->e2->op == TOKsymoff) 715 return; 716 ret = Min(e->loc, e->type, e->e1, e->e2).copy(); 717 } 718 } 719 720 void visit(MulExp *e) 721 { 722 //printf("MulExp::optimize(result = %d) %s\n", result, e->toChars()); 723 724 if (binOptimize(e, result)) 725 return; 726 727 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 728 { 729 ret = Mul(e->loc, e->type, e->e1, e->e2).copy(); 730 } 731 } 732 733 void visit(DivExp *e) 734 { 735 //printf("DivExp::optimize(%s)\n", e->toChars()); 736 737 if (binOptimize(e, result)) 738 return; 739 740 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 741 { 742 ret = Div(e->loc, e->type, e->e1, e->e2).copy(); 743 } 744 } 745 746 void visit(ModExp *e) 747 { 748 if (binOptimize(e, result)) 749 return; 750 751 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 752 { 753 ret = Mod(e->loc, e->type, e->e1, e->e2).copy(); 754 } 755 } 756 757 void shift_optimize(BinExp *e, UnionExp (*shift)(Loc, Type *, Expression *, Expression *)) 758 { 759 if (binOptimize(e, result)) 760 return; 761 762 if (e->e2->isConst() == 1) 763 { 764 sinteger_t i2 = e->e2->toInteger(); 765 d_uns64 sz = e->e1->type->size(); 766 assert(sz != SIZE_INVALID); 767 sz *= 8; 768 if (i2 < 0 || (d_uns64)i2 >= sz) 769 { 770 e->error("shift by %lld is outside the range 0..%llu", i2, (ulonglong)sz - 1); 771 return error(); 772 } 773 if (e->e1->isConst() == 1) 774 ret = (*shift)(e->loc, e->type, e->e1, e->e2).copy(); 775 } 776 } 777 778 void visit(ShlExp *e) 779 { 780 //printf("ShlExp::optimize(result = %d) %s\n", result, e->toChars()); 781 shift_optimize(e, &Shl); 782 } 783 784 void visit(ShrExp *e) 785 { 786 //printf("ShrExp::optimize(result = %d) %s\n", result, e->toChars()); 787 shift_optimize(e, &Shr); 788 } 789 790 void visit(UshrExp *e) 791 { 792 //printf("UshrExp::optimize(result = %d) %s\n", result, toChars()); 793 shift_optimize(e, &Ushr); 794 } 795 796 void visit(AndExp *e) 797 { 798 if (binOptimize(e, result)) 799 return; 800 801 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 802 ret = And(e->loc, e->type, e->e1, e->e2).copy(); 803 } 804 805 void visit(OrExp *e) 806 { 807 if (binOptimize(e, result)) 808 return; 809 810 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 811 ret = Or(e->loc, e->type, e->e1, e->e2).copy(); 812 } 813 814 void visit(XorExp *e) 815 { 816 if (binOptimize(e, result)) 817 return; 818 819 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 820 ret = Xor(e->loc, e->type, e->e1, e->e2).copy(); 821 } 822 823 void visit(PowExp *e) 824 { 825 if (binOptimize(e, result)) 826 return; 827 828 // Replace 1 ^^ x or 1.0^^x by (x, 1) 829 if ((e->e1->op == TOKint64 && e->e1->toInteger() == 1) || 830 (e->e1->op == TOKfloat64 && e->e1->toReal() == CTFloat::one)) 831 { 832 ret = new CommaExp(e->loc, e->e2, e->e1); 833 ret->type = e->type; 834 return; 835 } 836 837 // Replace -1 ^^ x by (x&1) ? -1 : 1, where x is integral 838 if (e->e2->type->isintegral() && e->e1->op == TOKint64 && (sinteger_t)e->e1->toInteger() == -1L) 839 { 840 ret = new AndExp(e->loc, e->e2, new IntegerExp(e->loc, 1, e->e2->type)); 841 ret->type = e->e2->type; 842 ret = new CondExp(e->loc, ret, new IntegerExp(e->loc, -1L, e->type), new IntegerExp(e->loc, 1L, e->type)); 843 ret->type = e->type; 844 return; 845 } 846 847 // Replace x ^^ 0 or x^^0.0 by (x, 1) 848 if ((e->e2->op == TOKint64 && e->e2->toInteger() == 0) || 849 (e->e2->op == TOKfloat64 && e->e2->toReal() == CTFloat::zero)) 850 { 851 if (e->e1->type->isintegral()) 852 ret = new IntegerExp(e->loc, 1, e->e1->type); 853 else 854 ret = new RealExp(e->loc, CTFloat::one, e->e1->type); 855 856 ret = new CommaExp(e->loc, e->e1, ret); 857 ret->type = e->type; 858 return; 859 } 860 861 // Replace x ^^ 1 or x^^1.0 by (x) 862 if ((e->e2->op == TOKint64 && e->e2->toInteger() == 1) || 863 (e->e2->op == TOKfloat64 && e->e2->toReal() == CTFloat::one)) 864 { 865 ret = e->e1; 866 return; 867 } 868 869 // Replace x ^^ -1.0 by (1.0 / x) 870 if ((e->e2->op == TOKfloat64 && e->e2->toReal() == CTFloat::minusone)) 871 { 872 ret = new DivExp(e->loc, new RealExp(e->loc, CTFloat::one, e->e2->type), e->e1); 873 ret->type = e->type; 874 return; 875 } 876 877 // All other negative integral powers are illegal 878 if ((e->e1->type->isintegral()) && (e->e2->op == TOKint64) && (sinteger_t)e->e2->toInteger() < 0) 879 { 880 e->error("cannot raise %s to a negative integer power. Did you mean (cast(real)%s)^^%s ?", 881 e->e1->type->toBasetype()->toChars(), e->e1->toChars(), e->e2->toChars()); 882 return error(); 883 } 884 885 // If e2 *could* have been an integer, make it one. 886 if (e->e2->op == TOKfloat64 && (e->e2->toReal() == ldouble((sinteger_t)e->e2->toReal()))) 887 e->e2 = new IntegerExp(e->loc, e->e2->toInteger(), Type::tint64); 888 889 if (e->e1->isConst() == 1 && e->e2->isConst() == 1) 890 { 891 Expression *ex = Pow(e->loc, e->type, e->e1, e->e2).copy(); 892 if (!CTFEExp::isCantExp(ex)) 893 { 894 ret = ex; 895 return; 896 } 897 } 898 899 // (2 ^^ n) ^^ p -> 1 << n * p 900 if (e->e1->op == TOKint64 && e->e1->toInteger() > 0 && 901 !((e->e1->toInteger() - 1) & e->e1->toInteger()) && 902 e->e2->type->isintegral() && e->e2->type->isunsigned()) 903 { 904 dinteger_t i = e->e1->toInteger(); 905 dinteger_t mul = 1; 906 while ((i >>= 1) > 1) 907 mul++; 908 Expression *shift = new MulExp(e->loc, e->e2, new IntegerExp(e->loc, mul, e->e2->type)); 909 shift->type = e->e2->type; 910 shift = shift->castTo(NULL, Type::tshiftcnt); 911 ret = new ShlExp(e->loc, new IntegerExp(e->loc, 1, e->e1->type), shift); 912 ret->type = e->type; 913 return; 914 } 915 } 916 917 void visit(CommaExp *e) 918 { 919 //printf("CommaExp::optimize(result = %d) %s\n", result, e->toChars()); 920 // Comma needs special treatment, because it may 921 // contain compiler-generated declarations. We can interpret them, but 922 // otherwise we must NOT attempt to constant-fold them. 923 // In particular, if the comma returns a temporary variable, it needs 924 // to be an lvalue (this is particularly important for struct constructors) 925 926 expOptimize(e->e1, WANTvalue); 927 expOptimize(e->e2, result, keepLvalue); 928 if (ret->op == TOKerror) 929 return; 930 931 if (!e->e1 || e->e1->op == TOKint64 || e->e1->op == TOKfloat64 || !hasSideEffect(e->e1)) 932 { 933 ret = e->e2; 934 if (ret) 935 ret->type = e->type; 936 } 937 938 //printf("-CommaExp::optimize(result = %d) %s\n", result, e->e->toChars()); 939 } 940 941 void visit(ArrayLengthExp *e) 942 { 943 //printf("ArrayLengthExp::optimize(result = %d) %s\n", result, e->toChars()); 944 945 if (unaOptimize(e, WANTexpand)) 946 return; 947 948 // CTFE interpret static immutable arrays (to get better diagnostics) 949 if (e->e1->op == TOKvar) 950 { 951 VarDeclaration *v = ((VarExp *)e->e1)->var->isVarDeclaration(); 952 if (v && (v->storage_class & STCstatic) && (v->storage_class & STCimmutable) && v->_init) 953 { 954 if (Expression *ci = v->getConstInitializer()) 955 e->e1 = ci; 956 } 957 } 958 959 if (e->e1->op == TOKstring || e->e1->op == TOKarrayliteral || e->e1->op == TOKassocarrayliteral || 960 e->e1->type->toBasetype()->ty == Tsarray) 961 { 962 ret = ArrayLength(e->type, e->e1).copy(); 963 } 964 } 965 966 void visit(EqualExp *e) 967 { 968 //printf("EqualExp::optimize(result = %x) %s\n", result, e->toChars()); 969 if (binOptimize(e, WANTvalue)) 970 return; 971 972 Expression *e1 = fromConstInitializer(result, e->e1); 973 Expression *e2 = fromConstInitializer(result, e->e2); 974 if (e1->op == TOKerror) 975 { 976 ret = e1; 977 return; 978 } 979 if (e2->op == TOKerror) 980 { 981 ret = e2; 982 return; 983 } 984 985 ret = Equal(e->op, e->loc, e->type, e1, e2).copy(); 986 if (CTFEExp::isCantExp(ret)) 987 ret = e; 988 } 989 990 void visit(IdentityExp *e) 991 { 992 //printf("IdentityExp::optimize(result = %d) %s\n", result, e->toChars()); 993 994 if (binOptimize(e, WANTvalue)) 995 return; 996 997 if ((e->e1->isConst() && e->e2->isConst()) || 998 (e->e1->op == TOKnull && e->e2->op == TOKnull) 999 ) 1000 { 1001 ret = Identity(e->op, e->loc, e->type, e->e1, e->e2).copy(); 1002 if (CTFEExp::isCantExp(ret)) 1003 ret = e; 1004 } 1005 } 1006 1007 /* It is possible for constant folding to change an array expression of 1008 * unknown length, into one where the length is known. 1009 * If the expression 'arr' is a literal, set lengthVar to be its length. 1010 */ 1011 static void setLengthVarIfKnown(VarDeclaration *lengthVar, Expression *arr) 1012 { 1013 if (!lengthVar) 1014 return; 1015 if (lengthVar->_init && !lengthVar->_init->isVoidInitializer()) 1016 return; // we have previously calculated the length 1017 size_t len; 1018 if (arr->op == TOKstring) 1019 len = ((StringExp *)arr)->len; 1020 else if (arr->op == TOKarrayliteral) 1021 len = ((ArrayLiteralExp *)arr)->elements->dim; 1022 else 1023 { 1024 Type *t = arr->type->toBasetype(); 1025 if (t->ty == Tsarray) 1026 len = (size_t)((TypeSArray *)t)->dim->toInteger(); 1027 else 1028 return; // we don't know the length yet 1029 } 1030 1031 Expression *dollar = new IntegerExp(Loc(), len, Type::tsize_t); 1032 lengthVar->_init = new ExpInitializer(Loc(), dollar); 1033 lengthVar->storage_class |= STCstatic | STCconst; 1034 } 1035 1036 void visit(IndexExp *e) 1037 { 1038 //printf("IndexExp::optimize(result = %d) %s\n", result, e->toChars()); 1039 if (expOptimize(e->e1, result & WANTexpand)) 1040 return; 1041 1042 Expression *ex = fromConstInitializer(result, e->e1); 1043 1044 // We might know $ now 1045 setLengthVarIfKnown(e->lengthVar, ex); 1046 1047 if (expOptimize(e->e2, WANTvalue)) 1048 return; 1049 if (keepLvalue) 1050 return; 1051 ret = Index(e->type, ex, e->e2).copy(); 1052 if (CTFEExp::isCantExp(ret)) 1053 ret = e; 1054 } 1055 1056 void visit(SliceExp *e) 1057 { 1058 //printf("SliceExp::optimize(result = %d) %s\n", result, e->toChars()); 1059 if (expOptimize(e->e1, result & WANTexpand)) 1060 return; 1061 if (!e->lwr) 1062 { 1063 if (e->e1->op == TOKstring) 1064 { 1065 // Convert slice of string literal into dynamic array 1066 Type *t = e->e1->type->toBasetype(); 1067 if (Type *tn = t->nextOf()) 1068 ret = e->e1->castTo(NULL, tn->arrayOf()); 1069 } 1070 } 1071 else 1072 { 1073 e->e1 = fromConstInitializer(result, e->e1); 1074 // We might know $ now 1075 setLengthVarIfKnown(e->lengthVar, e->e1); 1076 expOptimize(e->lwr, WANTvalue); 1077 expOptimize(e->upr, WANTvalue); 1078 if (ret->op == TOKerror) 1079 return; 1080 ret = Slice(e->type, e->e1, e->lwr, e->upr).copy(); 1081 if (CTFEExp::isCantExp(ret)) 1082 ret = e; 1083 } 1084 1085 // Bugzilla 14649: We need to leave the slice form so it might be 1086 // a part of array operation. 1087 // Assume that the backend codegen will handle the form `e[]` 1088 // as an equal to `e` itself. 1089 if (ret->op == TOKstring) 1090 { 1091 e->e1 = ret; 1092 e->lwr = NULL; 1093 e->upr = NULL; 1094 ret = e; 1095 } 1096 //printf("-SliceExp::optimize() %s\n", ret->toChars()); 1097 } 1098 1099 void visit(AndAndExp *e) 1100 { 1101 //printf("AndAndExp::optimize(%d) %s\n", result, e->toChars()); 1102 if (expOptimize(e->e1, WANTvalue)) 1103 return; 1104 1105 if (e->e1->isBool(false)) 1106 { 1107 // Replace with (e1, false) 1108 ret = new IntegerExp(e->loc, 0, Type::tbool); 1109 ret = Expression::combine(e->e1, ret); 1110 if (e->type->toBasetype()->ty == Tvoid) 1111 { 1112 ret = new CastExp(e->loc, ret, Type::tvoid); 1113 ret->type = e->type; 1114 } 1115 return; 1116 } 1117 1118 if (expOptimize(e->e2, WANTvalue)) 1119 return; 1120 1121 if (e->e1->isConst()) 1122 { 1123 if (e->e2->isConst()) 1124 { 1125 bool n1 = e->e1->isBool(true); 1126 bool n2 = e->e2->isBool(true); 1127 ret = new IntegerExp(e->loc, n1 && n2, e->type); 1128 } 1129 else if (e->e1->isBool(true)) 1130 { 1131 if (e->type->toBasetype()->ty == Tvoid) 1132 ret = e->e2; 1133 else 1134 { 1135 ret = new CastExp(e->loc, e->e2, e->type); 1136 ret->type = e->type; 1137 } 1138 } 1139 } 1140 } 1141 1142 void visit(OrOrExp *e) 1143 { 1144 //printf("OrOrExp::optimize(%d) %s\n", result, e->toChars()); 1145 if (expOptimize(e->e1, WANTvalue)) 1146 return; 1147 1148 if (e->e1->isBool(true)) 1149 { 1150 // Replace with (e1, true) 1151 ret = new IntegerExp(e->loc, 1, Type::tbool); 1152 ret = Expression::combine(e->e1, ret); 1153 if (e->type->toBasetype()->ty == Tvoid) 1154 { 1155 ret = new CastExp(e->loc, ret, Type::tvoid); 1156 ret->type = e->type; 1157 } 1158 return; 1159 } 1160 1161 if (expOptimize(e->e2, WANTvalue)) 1162 return; 1163 1164 if (e->e1->isConst()) 1165 { 1166 if (e->e2->isConst()) 1167 { 1168 bool n1 = e->e1->isBool(true); 1169 bool n2 = e->e2->isBool(true); 1170 ret = new IntegerExp(e->loc, n1 || n2, e->type); 1171 } 1172 else if (e->e1->isBool(false)) 1173 { 1174 if (e->type->toBasetype()->ty == Tvoid) 1175 ret = e->e2; 1176 else 1177 { 1178 ret = new CastExp(e->loc, e->e2, e->type); 1179 ret->type = e->type; 1180 } 1181 } 1182 } 1183 } 1184 1185 void visit(CmpExp *e) 1186 { 1187 //printf("CmpExp::optimize() %s\n", e->toChars()); 1188 if (binOptimize(e, WANTvalue)) 1189 return; 1190 1191 Expression *e1 = fromConstInitializer(result, e->e1); 1192 Expression *e2 = fromConstInitializer(result, e->e2); 1193 1194 ret = Cmp(e->op, e->loc, e->type, e1, e2).copy(); 1195 if (CTFEExp::isCantExp(ret)) 1196 ret = e; 1197 } 1198 1199 void visit(CatExp *e) 1200 { 1201 //printf("CatExp::optimize(%d) %s\n", result, e->toChars()); 1202 1203 if (binOptimize(e, result)) 1204 return; 1205 1206 if (e->e1->op == TOKcat) 1207 { 1208 // Bugzilla 12798: optimize ((expr ~ str1) ~ str2) 1209 CatExp *ce1 = (CatExp *)e->e1; 1210 CatExp cex(e->loc, ce1->e2, e->e2); 1211 cex.type = e->type; 1212 Expression *ex = cex.optimize(result); 1213 if (ex != &cex) 1214 { 1215 e->e1 = ce1->e1; 1216 e->e2 = ex; 1217 } 1218 } 1219 1220 // optimize "str"[] -> "str" 1221 if (e->e1->op == TOKslice) 1222 { 1223 SliceExp *se1 = (SliceExp *)e->e1; 1224 if (se1->e1->op == TOKstring && !se1->lwr) 1225 e->e1 = se1->e1; 1226 } 1227 if (e->e2->op == TOKslice) 1228 { 1229 SliceExp *se2 = (SliceExp *)e->e2; 1230 if (se2->e1->op == TOKstring && !se2->lwr) 1231 e->e2 = se2->e1; 1232 } 1233 1234 ret = Cat(e->type, e->e1, e->e2).copy(); 1235 if (CTFEExp::isCantExp(ret)) 1236 ret = e; 1237 } 1238 1239 void visit(CondExp *e) 1240 { 1241 if (expOptimize(e->econd, WANTvalue)) 1242 return; 1243 if (e->econd->isBool(true)) 1244 ret = e->e1->optimize(result, keepLvalue); 1245 else if (e->econd->isBool(false)) 1246 ret = e->e2->optimize(result, keepLvalue); 1247 else 1248 { 1249 expOptimize(e->e1, result, keepLvalue); 1250 expOptimize(e->e2, result, keepLvalue); 1251 } 1252 } 1253 }; 1254 1255 OptimizeVisitor v(result, keepLvalue); 1256 Expression *ex = NULL; 1257 v.ret = e; 1258 1259 // Optimize the expression until it can no longer be simplified. 1260 size_t b = 0; 1261 while (1) 1262 { 1263 if (b++ == global.recursionLimit) 1264 { 1265 e->error("infinite loop while optimizing expression"); 1266 fatal(); 1267 } 1268 ex = v.ret; 1269 ex->accept(&v); 1270 if (ex == v.ret) 1271 break; 1272 } 1273 return ex; 1274} 1275