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