ddmd.optimize source code

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