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
24 Expression *semantic(Expression *e, Scope *sc);
25
26 /*************************************
27 * If variable has a const initializer,
28 * return that initializer.
29 */
30
expandVar(int result,VarDeclaration * v)31 Expression *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 }
135 L1:
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
139 Lerror:
140 return new ErrorExp();
141 }
142
143
fromConstInitializer(int result,Expression * e1)144 Expression *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
Expression_optimize(Expression * e,int result,bool keepLvalue)179 Expression *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